24130262
Geometric Knapsack Problems
We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following “fence enclosure” problem: Given a set S of n points in the plane with values v i ≥ 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the “value” of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowing S to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of up to K connected components. When there is an upper bound on the length of fence available, we show that the problem is N P-complete. Additionally we provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.
207132060
Terrain Decomposition and Layered Manufacturing
We consider a problem that arises in generating three-dimensional models by methods of layered manufacturing: How does one decompose a given model P into a small number of sub-models each of which is a terrain polyhedron? Terrain polyhedra have a base facet such that, for each point of the polyhedron, the line segment joining the point to its orthogonal projection on the base facet lies within the polyhedron. Terrain polyhedra are exactly the class of polyhedral models for which it is possible to construct the model using layered manufacturing (with layers parallel to the base facet), without the need for constructing "supports" (which must later be removed). In order to maximize the integrity of a prototype, one wants to minimize the number of individual sub-models that are manufactured and then glued together. We show that it is NP-hard to decide if a three-dimensional model P of genus 0 can be decomposed into k terrain polyhedra. We also prove a two-dimensional version of this theorem, for the case in which P is a polygonal region with holes. Both results still hold if we are restricted to isothetic objects and/or axis-parallel layering directions.
7753820
Approximate Geometric Pattern Matching Under Rigid Motions
We present techniques for matching point-sets in two and three dimensions under rigid-body transformations. We prove bounds on the worst-case performance of these algorithms to be within a small constant factor of optimal and conduct experiments to show that the average performance of these matching algorithms is often better than that predicted by the worst-case bounds.
11557966
An algorithmic study of manufacturing paperclips and other folded structures
We study algorithmic aspects of bending wires and sheet metal into a specified structure. Problems of this type are closely related to the question of deciding whether a simple non-self-intersecting wire structure (a carpenter's ruler) can be straightened, a problem that was open for several years and has only recently been solved in the affirmative. If we impose some of the constraints that are imposed by the manufacturing process, we obtain quite different results. In particular, we study the variant of the carpenter's ruler problem in which there is a restriction that only one joint can be modified at a time. For a linkage that does not self-intersect or self-touch, the recent results of Connelly et al. and Streinu imply that it can always be straightened, modifying one joint at a time. However, we show that for a linkage with even a single vertex degeneracy, it becomes NP-hard to decide if it can be straightened while altering only one joint at a time. If we add the restriction that each joint can be altered at most once, we show that the problem is NP-complete even without vertex degeneracies. In the special case, arising in wire forming manufacturing, that each joint can be altered at most once, and must be done sequentially from one or both ends of the linkage, we give an efficient algorithm to determine if a linkage can be straightened.
57900050
Computational Geometry Column 42
A compendium of thirty previously published open problems in computational geometry is presented.
16007270
Point Probe Decision Trees for Geometric Concept Classes
A fundamental problem in model-based computer vision is that of identifying to which of a given set of concept classes of geometric models an observed model belongs. Considering a “probe” to be an oracle that tells whether or not the observed model is present at a given point in an image, we study the problem of computing efficient strategies (“decision trees”) for probing an image, with the goal to minimize the number of probes necessary (in the worst case) to determine in which class the observed model belongs. We prove a hardness result and give strategies that obtain decision trees whose height is within a log factor of optimal.
7541818
A type system for object initialization in the Java bytecode language
In the standard Java implementation, a Java language program is compiled to Java bytecode. This bytecode may be sent across the network to another site, where it is then interpreted by the Java Virtual Machine. Since bytecode may be written by hand, or corrupted during network transmission, the Java Virtual Machine contains a bytecode verifier that performs a number of consistency checks before code is interpreted. As illustrated by previous attacks on the Java Virtual Machine, these tests, which include type correctness, are critical for system security. In order to analyze existing bytecode verifiers and to understand the properties that should be verified, we develop a precise specification of statically-correct Java bytecode, in the form of a type system. Our focus in this paper is a subset of the bytecode language dealing with object creation and initialization. For this subset, we prove that for every Java bytecode program that satisfies our typing constraints, every object is initialized before it is used. The type system is easily combined with a previous system developed by Stata and Abadi for bytecode subroutines. Our analysis of subroutines and object initialization reveals a previously unpublished bug in the Sun JDK bytecode verifier.
2523975
Multiset rewriting and the complexity of bounded security protocols
We formalize the Dolev-Yao model of security protocols, using a notation based on multiset rewriting with existentials. The goals are to provide a simple formal notation for describing security protocols, to formalize the assumptions of the Dolev-Yao model using this notation, and to analyze the complexity of the secrecy problem under various restrictions. We prove that, even for the case where we restrict the size of messages and the depth of message encryption, the secrecy problem is undecidable for the case of an unrestricted number of protocol roles and an unbounded number of new nonces. We also identify several decidable classes, including a DEXP-complete class when the number of nonces is restricted, and an NP-complete class when both the number of nonces and the number of roles is restricted. We point out a remaining open complexity problem, and discuss the implications these results have on the general topic of protocol analysis.
15188207
RT: a Role-based Trust-management framework
The RT Role-based Trust-management framework provides policy language, semantics, deduction engine, and pragmatic features such as application domain specification documents that help distributed users maintain consistent use of policy terms. This paper provides a general overview of the framework, combining some aspects described in previous publications with recent improvements and explanation of motivating applications.
2148906
Type Inference With Simple Subtypes
ion clause, we use A -{x: σ} to denote the set difference, i.e., the type assignment defined by removing x: σ from A. G(x) = { s⊆t }, { x:s} ⊃ x:t G(MN) = let C1, A1 ⊃ M:σ = G(M) C2, A2 ⊃ N:τ = G(N), with type variables renamed to be disjoint from those in G(M) S = UNIFY({ α=β | x:α∈A1 and x:β∈A2} ∪ { σ=τ→t}) where t is a fresh type variable in SC1∪SC2∪{St⊆u}, SA1∪SA2 ⊃ MN:u where u is a fresh type variable G(λx.M) = let C, A ⊃ M:τ = G(M) in if x:σ∈A for someσ then C∪{ σ→τ⊆u}, (A -{x: σ}) ⊃ λx.M:u else C∪{s→τ⊆u}, A ⊃ λx.M:u, where s, u are fresh type variables The algorithm could concei vably fail in the application case if the call to UNIFY fails. Howev er, we will see that this does not happen. It is not to hard to pro ve that if G(M) succeeds, then it produces a pro vable typing for M. THEOREM 13. If G(M) = C,A ⊃ M:σ, then− C,A⊃ M:σ. It follows, by Lemma 11, that e v ry instance of G(M) is a pro vable typing for M. Conversely, every provable typing for M is an instance of G(M). THEOREM 14. Suppose− C,A ⊃ M:σ. Then G(M) succeeds and produces a typing with C,A⊃ M:σ as an instance. Both theorems are pro ved below. From Lemma 2, we kno w that every term has a pro vable CC typing. Therefore, Theorem 14 implies G(M) al ways succeeds.
5553551
Decision Problems for Propositional Linear Logic
Abstract Linear logic, introduced by Girard, is a refinement of classical logic with a natural, intrinsic accounting of resources. This accounting is made possible by removing the ‘structural’ rules of contraction and weakening, adding a modal operator and adding finer versions of the propositional connectives. Linear logic has fundamental logical interest and applications to computer science, particularly to Petri nets, concurrency, storage allocation, garbage collection and the control structure of logic programs. In addition, there is a direct correspondence between polynomial-time computation and proof normalization in a bounded form of linear logic. In this paper we show that unlike most other propositional (quantifier-free) logics, full propositional linear logic is undecidable. Further, we prove that without the modal storage operator, which indicates unboundedness of resources, the decision problem becomes PSPACE-complete. We also establish membership in NP for the multiplicative fragment, NP-completeness for the multiplicative fragment extended with unrestricted weakening, and undecidability for fragments of noncommutative propositional linear logic.