28274388
Query-Sensitive Ray Shooting
Ray (segment) shooting is the problem of determining the first intersection between a ray (directed line segment) and a collection of polygonal or polyhedral obstacles. In order to process queries efficiently, the set of obstacle polyhedra is usually preprocessed into a data structure. In this paper we propose a query-sensitive data structure for ray shooting, which means that the performance of our data structure depends on the local geometry of obstacles near the query segment. We measure the complexity of the local geometry near the segment by a parameter called the simple cover complexity, denoted by scc(s) for a segment s. Our data structure consists of a subdivision that partitions the space into a collection of polyhedral cells, each of O(1) complexity. We answer a segment shooting query by wallking along the segment through the subdivision. Our first result is that, for any fixed dimension d, there exists a simple hierarchical subdivision in which no query segment s intersects more than O(scc(s)) cells. Our second result shows that in two dimensions such a subdivision of size O(n) can be constructed in time O(nlogn), where n is the total number of vertices in all the obstacles.
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.
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.
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.
57900050
Computational Geometry Column 42
A compendium of thirty previously published open problems in computational geometry is presented.
8879002
Status of clinical gene sequencing data reporting and associated risks for information loss
Clinical gene sequencing is growing in importance and cost-effectiveness. In the past two years, the number of genes associated with disease has grown by roughly 25%. Knowledge of genetic variations will soon guide drug selection and dosages, predict risks from toxin exposures, and inform nutritional needs. Despite the significance of sequencing, methods for reporting results are problematic. Frequent use of paper and infrequent use of naming standards impede data exchange and make incorporation into the electronic medical record difficult. Reports often describe only variations found, rather than all data (all patient bases sequenced). Also, reports frequently do not describe reference data used to define variations. These practices create risks for loss of both data and information. Standardized electronic reporting of all data (all bases sequenced and all reference data) and electronic record systems capable of storing these results would both prevent data loss and simplify the preservation of information those data provide.
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.
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.
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.
12005506
Kripke-Style Models for Typed lambda Calculus
The semantics of typed lambda calculus is usually described using Henkin models, consisting of functions over some collection of sets, or concrete cartesian closed categories, which are essentially equivalent. We describe a more general class of Kripte-style models. In categorical terms, our Kripke lambda models are cartesian closed subcategories of the presheaves over a poset. While the traditional lambda calculus proof system is not complete for Henkin models that may have empty types, we prove strong completeness for Kripke models. In fact, every set of equations that is closed under implication is the theory of a single Kripke model. We develop some properties of logical relations over Kripke structures, showing that every theory if the theory of a model determined by a Kripke equivalence relation over a Henkin model