16824358
On Minimum-Area Hulls
Abstract. We study some minimum-area hull problems that generalize the notion of convex hull to star-shaped and monotone hulls. Specifically, we consider the minimum-area star-shaped hull problem: Given an n -vertex simple polygon P , find a minimum-area, star-shaped polygon P* containing P . This problem arises in lattice packings of translates of multiple, nonidentical shapes in material layout problems (e.g., in clothing manufacture), and has been recently posed by Daniels and Milenkovic. We consider two versions of the problem: the restricted version, in which the vertices of P* are constrained to be vertices of P , and the unrestricted version, in which the vertices of P* can be anywhere in the plane. We prove that the restricted problem falls in the class of ``3sum-hard'' (sometimes called ``n2 -hard'') problems, which are suspected to admit no solutions in o(n2) time. Further, we give an O(n2) time algorithm, improving the previous bound of O(n5) . We also show that the unrestricted problem can be solved in O(n2 p(n)) time, where p(n) is the time needed to find the roots of two equations in two unknowns, each a polynomial of degree O(n) . We also consider the case in which P* is required to be monotone, with respect to an unspecified direction; we refer to this as the minimum-area monotone hull problem. We give a matching lower and upper bound of Θ(n log n) time for computing P* in the restricted version, and an upper bound of O(n q(n)) time in the unrestricted version, where q(n) is the time needed to find the roots of two polynomial equations in two unknowns with degrees 2 and O(n) .
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.
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.
11133086
Query-sensitive ray shooting
Ray shooting is the problem of determining the first intersection of a ray with a set of obstacies. We assume that obstacles are modeled as polygons in the plane, or generally polyhedra in higher dimensions. Since many ray shooting queries may be applied to a given set of obstacles, it is desirable to preprocess the obstacles so that query processing is as efficient as possible. The problem of ray shooting in a simple polygon with n vertices haa been studied by [7, 6, 10]. In all cases, with linear space, ray shooting queries can be answered in O(log n) time. Ray shooting amidst a set of polygonal obstacles has been considered by [1, 6, 8, 10, 15]. In all these cases, space is within a polylogarithmic factor of linear, and the best query time is O(fi log n) query time. One of the shortcomings of these approaches is that they fail to account for the geometric structure of the obstacle set and query ray. Analyses based solely upon input size cannot account for the fact that, for a fixed in-
57900050
Computational Geometry Column 42
A compendium of thirty previously published open problems in computational geometry is presented.
7795941
Specifying and verifying hardware for tamper-resistant software
We specify a hardware architecture that supports tamper-resistant software by identifying an "idealized" model, which gives the abstracted actions available to a single user program. This idealized model is compared to a concrete "actual" model that includes actions of an adversarial operating system. The architecture is verified by using a finite-state enumeration tool (a model checker) to compare executions of the idealized and actual models. In this approach, software tampering occurs if the system can enter a state where one model is inconsistent with the other in performing the verification, we detected a replay attack scenario and were able to verify the security of our solution to the problem. Our methods were also able to verify that all actions in the architecture are required, as well as come up with a set of constraints on the operating system to guarantee liveness for users.
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.
14904191
Games and the Impossibility of Realizable Ideal Functionality
A cryptographic primitive or a security mechanism can be specified in a variety of ways, such as a condition involving a game against an attacker, construction of an ideal functionality, or a list of properties that must hold in the face of attack. While game conditions are widely used, an ideal functionality is appealing because a mechanism that is indistinguishable from an ideal functionality is therefore guaranteed secure in any larger system that uses it. We relate ideal functionalities to games by defining the set of ideal functionalities associated with a game condition and show that under this definition, which reflects accepted use and known examples, bit commitment, a form of group signatures, and some other cryptographic concepts do not have any realizable ideal functionality.
14607433
Lower bounds on type inference with subtypes
We investigate type inference for programming languages with subtypes. As described in previous work, there are several type inference problems for any given expression language, depending on the form of the subtype partial order and the ability to define new subtypes in programs. Our first main result is that for any specific subtype partial order, the problem of determining whether a lambda term is typable is algorithmically (polynomial-time) equivalent to a form of satisfiability problem over the same partial order. This gives the first exact characterization of the problem that is independent of the syntax of expressions. In addition, since this form of satisfiability problem is PSPACE-hard over certain partial orders, this equivalence strengthens the previous lower bound of NP-hard to PSPACE-hard. Our second main result is a lower bound on the length of most general types when the subtype hierarchy may change as a result of additional type declarations within the program. More specifically, given any input expression, a type inference algorithm tries to find a most general (or principal) typing. The property of a most general typing is that it has all other possible typings as instances. However, there are several sound notions of instance in the presence of subtyping. Our lower bound is that no sound definition of instance would allow the set of additional subtyping hypotheses about a term to grow less than linearly in the size of the term.
35130740
Decision problems for propositional linear logic
It is shown that, unlike most other propositional (quantifier-free) logics, full propositional linear logic is undecidable. Further, it is provided that without the model storage operator, which indicates unboundedness of resources, the decision problem becomes PSPACE-complete. Also established are membership in NP for the multiplicative fragment, NP-completeness for the multiplicative fragment extended with unrestricted weakening, and undecidability for certain fragments of noncommutative propositional linear logic.<<ETX>>