14267496
Recognizing polygonal parts from width measurements
Abstract Automatic recognition of parts is an important problem in many industrial applications. One model of the problem is: given a finite set of polygonal parts, use a set of “width” measurements taken by a parallel-jaw gripper to determine which part is present. We study the problem of computing efficient strategies (“grasp plans”), with the goal to minimize the number of measurements necessary in the worst case. We show that finding a minimum length grasp plan is NP -hard, and give a polynomial time approximation algorithm that is simple and produces a solution that is within a log factor from 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.
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.
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.
57900050
Computational Geometry Column 42
A compendium of thirty previously published open problems in computational geometry is presented.
14058328
Autonomous Nodes and Distributed Mechanisms
We extend distributed algorithmic mechanism design by considering a new model that allows autonomous nodes executing a distributed mechanism to strategically deviate from the prescribed protocol. Our goal is to motivate agents to contribute to a global objective and resist disruption by a limited number of malicious irrational agents, augmenting market incentives with cryptographic primitives to make certain forms of behavior computationally infeasible. Several techniques for distributing market computation among autonomous agents are illustrated using a marginal cost mechanism for multicast cost sharing from.
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.
3062362
Managing Digital Rights using Linear Logic
Digital music players protect songs by enforcing licenses that convey specific rights for individual songs or groups of songs. For licenses specified in industry, we show that deciding whether a license authorizes a sequence of actions is NP-complete, with a restricted version of the problem solvable efficiently using a reduction to maximum network flow. The authorization algorithm used in industry is online, deciding which rights to exercise as actions occur, but we show that all online algorithms are necessarily non-monotonic: each allows actions under one license that it does not allow under a more flexible license. In one approach to achieving monotonicity, we exhibit the unique maximal set of licenses on which there exists a monotonic online algorithm. This set of well-behaved licenses induces an approximation algorithm by replacing each license with a well-behaved license. In a second approach, we consider allowing the player to revise its past decisions about which rights to exercise while still ensuring compliance with the license. We propose an efficient algorithm based on linear logic, with linear negation used to revise past decisions. We prove our algorithm monotonic, live, and sound with respect to the semantics of licenses
10533033
On the Sequential Nature of Unification
Abstract The problem of unification of terms is log-space complete for P. In deriving this lower bound no use is made of the potentially concise representation of terms by directed acyclic graphs. In addition, the problem remains complete even if infinite substitutions are allowed. A consequence of this result is that parallelism cannot significantly improve on the best sequential solutions for unification. However, we show that for the problem of term matching, an important subcase of unification, there is a good parallel algorithm using O ( log 2 n ) time and n O(1) processors on a PRAM. For the O ( log 2 n ) parallel time upper bound we assume that the terms are represented by directed acyclic graphs; if the longer string representation is used we obtain an O ( log n ) parallel time bound.
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.