12454813
Orthogonal segment stabbing
We study a class of geometric stabbing/covering problems for sets of line segments, rays and lines in the plane. While we demonstrate that the problems on sets of horizontal/vertical line segments are NP-complete, we show that versions involving (parallel) rays or lines are polynomially solvable.
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.
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.
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.
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.
10944537
The Complexity of Local Proof Search in Linear Logic
Abstract Proof search in linear logic is known to be difficult: the provability of propositional linear logic formulas is undecidable. Even without the modalities, multiplicative-additive fragment of propositional linear logic, mall , is known to be PSPACE-complete, and the pure multiplicative fragment, mll , is known to be np -complete. However, this still leaves open the possibility that there might be proof search heuristics (perhaps involving randomization) that often lead to a proof if there is one, or always lead to something close to a proof. One approach to these problems is to study strategies for proof games. A class of linear logic proof games is developed, each with a numeric score that depends on the number of certain preferred axioms used in a complete or partial proof tree. Using recent techniques for proving lower bounds on optimization problems, the complexity of these games is analyzed for the fragment mll extended with additive constants and for the fragment MALL. It is shown that no efficient heuristics exist unless there is an unexpected collapse in the complexity hierarchy.
7468814
Coupled optimization in protein docking
Here, we introduce a new approach to macromolecular docking which combines the continuous global optimization algorithm CGU [6, 21] with the grid-based conformational search engine DOT [23]. We also detail the use of this method to dock acetylcholine into the fasciculin-acetylcholinesterase complex. Fasciculin blocks access to the long, narrow pathway leading to the active site, which is located in the interior of the acetylcholinesterase. For this reason, flnding the location computationally is rather non-trivial. We not only successfully identifled the optimal docking conflguration, but were able to do so in a matter of hours.
5528932
On the Relationship Between Classes, Objects, and Data Abstraction
While most object-oriented programming is done in class-based languages, the trend in theoretical study has been to develop formal systems that are object-based, without classes and often without explicit inheritance mechanisms. This paper studies the correspondence between object primitives and class constructs of the form found in C++, Eiffel, and Java. The main qualitative insight is that such classes require both an extensible aggregate, to serve as the basis for inheritance, and a non-extensible form of object to support subtyping. We compare three approaches to modeling classes, the first using records of object components called “premethods” and the latter two using an extensible form of object called a “prototype.” While the first approach uses fewer primitive operations on objects, it does not provide several important features of class-based languages. In the latter two approaches, we overcome these deficiencies by combining prototypes with standard abstraction mechanisms. All three treatments of classes use translations into provably sound object calculi.
5176809
DATALOG with Constraints: A Foundation for Trust Management Languages
Trust management (TM) is a promising approach for authorization and access control in distributed systems, based on signed distributed policy statements expressed in a policy language. Although several TM languages are semantically equivalent to subsets of Datalog, Datalog is not sufficiently expressive for fine-grained control of structured resources. We define the class of linearly decomposable unary constraint domains, prove that DATALOG extended with constraints in any combination of such constraint domains is tractable, and show that permissions associated with structured resources fall into this class. We also present a concrete declarative TM language, RT1C, based on constraint DATALOG, and use constraint DATALOG to analyze another TM system, KeyNote, which turns out to be less expressive than RT1C in significant respects, yet less tractable in the worst case. Although constraint DATALOG has been studied in the context of constraint databases, TM applications involve different kinds of constraint domains and have different computational complexity requirements.
11514293
Analysis of a Fair Exchange Protocol
We analyze an optimistic contract signing protocol of Asokan, Shoup, and Waidner as a case study in the applicability of formal methods to verification of fair exchange protocols. After discussing the challenges involved in formalizing fairness, we use Mur , a finitestate analysis tool, to discover a weakness in the protocol that enables a malicious participant to produce inconsistent versions of the contract or mount a replay attack. We show that the protocol can be repaired, and that the confidentiality assumption about the communication channels may be relaxed while preserving security against the conventional Dolev-Yao intruder.