7524589
Sweeping simple polygons with a chain of guards
We consider the problem of locating a continuously-moving target using a group of guards moving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon such that consecutive guards along the chain are mutually visible. We develop algorithms that sweep such a chain of guards through a polygon to locate the target. Our two main results are the following: 1. an algorithm to compute the minimum number r∗ of guards needed to sweep an n-vertex polygon that runs in O(n) time and uses O(n) working space, and 2. a faster algorithm, using O(n log n) time and O(n) space, to compute an integer r such that max(r − 16, 2) ≤ r∗ ≤ r and P can be swept with a chain of r guards. We develop two other techniques to approximate r∗. Using O(n) time and space, we show how to sweep the polygon using at most r∗ +2 guards. We also show that any polygon can be swept by a number of guards equal to two more than the link radius of the polygon. As a key component of our exact algorithm, we introduce the notion of the link diagram of a polygon, which encodes the link distance between all pairs of points on the boundary of the polygon. We prove that the link diagram has size Θ(n) and can be constructed in Θ(n) time. We also show link diagram provides a data structure for optimal two-point link-distance queries, matching an earlier result of Arkin et al. As a key component of our O(n log n)-time approximation algorithm, we introduce the notion of the “link width” of a polygon, which may have independent interest, as it captures important structural properties of simple polygons. Computer Science Dept., Stanford University, 353 Serra Mall, Stanford CA 94305. Email: alon@cs.stanford.edu. Supported by a Rothschild Fellowship and by NSF research grant CCR-96-23851. Computer Science Dept., Stanford University, 353 Serra Mall, Stanford CA 94305. Email: guibas@cs.stanford.edu. Partially supported by DARPA grant DAAE07-98-C-L027 and by ARO MURI grant DAAH04-96-1-007. School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel. Email: sariel@math.tau.ac.il. Computer Science Dept., Stanford University, 353 Serra Mall, Stanford CA 94305. Email: dlin@cs.stanford.edu. Supported by DARPA grant DAAE07-98-C-L027 and by ARO MURI grant DAAH04-96-1-007. Dept. Applied Math, University at Stony Brook, Stony Brook, NY 11794-3600. Email: jsbm@ams.sunysb.edu. Partially supported by NSF (CCR-9732220), and grants from Hughes Research Labs, ISX Corporation, Seagull Technologies, NASA, and Sun Microsystems. Computer Science Dept., Stanford University, 353 Serra Mall, Stanford CA 94305. Email: murali@cs.stanford.edu. Supported by DARPA grant DAAE07-98-C-L027.
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.
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.
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.
17297807
Probabilistic Polynomial-Time Semantics for a Protocol Security Logic
We describe a cryptographically sound formal logic for proving protocol security properties without explicitly reasoning about probability, asymptotic complexity, or the actions of a malicious attacker. The approach rests on a new probabilistic, polynomial-time semantics for an existing protocol security logic, replacing an earlier semantics that uses nondeterministic symbolic evaluation. While the basic form of the protocol logic remains unchanged from previous work, there are some interesting technical problems involving the difference between efficiently recognizing and efficiently producing a value, and involving a reinterpretation of standard logical connectives that seems necessary to support certain forms of reasoning.
1569108
Distributed Credential Chain Discovery in Trust Management
We introduce a simple Role-based Trust-management language RT0 and a set-theoretic semantics for it. We also introduce credential graphs as a searchable representation of credentials in RT0 and prove that reachability in credential graphs is sound and complete with respect to the semantics of RT0. Based on credential graphs, we give goal-directed algorithms to do credential chain discovery in RT0, both when credential storage is centralized and when credential storage is distributed. A goal-directed algorithm begins with an access-control query and searches for credentials relevant to the query, while avoiding considering the potentially very large number of credentials that are unrelated to the access-control decision at hand. This approach provides better expected-case performance than bottom-up algorithms. We show how our algorithms can be applied to SDSI 2.0 (the 'SDSI' part of SPKI/SDSI 2.0).Our goal-directed, distributed chain discovery algorithm finds and retrieves credentials as needed. We prove that the algorithm is correct by proving that the algorithm is sound and complete with respect to the credential graph composed of the credentials it retrieves, and that the algorithm retrieves all credentials that constitute a traversable chain. We further introduce a storage type system for RT0, which guarantees traversability of chains when credentials are well typed. This type system can also help improve search efficiency by guiding search in the right direction, making distributed chain discovery with large number of credentials feasible.
17116402
Distributed credential chain discovery in trust management: extended abstract
We give goal-oriented algorithms for discovering credential chains in RTo, a role-based trust-management language introduced in this paper. The algorithms search credential graphs, a representation of RTo credentials. We prove that evaluation based on reachability in credential graphs is sound and complete with respect to the set-theoretic semantics of RTo . RTo is more expressive than SDSI 2.0, so our algorithms can perform chain discovery in SDSI 2.0, for which existing algorithms in the literature either are not goal-oriented or require using specialized logic-programming inferencing engines. Being goal-oriented enables our algorithms to be used when credential storage is distributed. We introduce a type system for credential storage that guarantees well-typed, distributed credential chains can be discovered.
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.
1936302
Communication and re-use of chemical information in bioscience
The current methods of publishing chemical information in bioscience articles are analysed. Using 3 papers as use-cases, it is shown that conventional methods using human procedures, including cut-and-paste are time-consuming and introduce errors. The meaning of chemical terms and the identity of compounds is often ambiguous. valuable experimental data such as spectra and computational results are almost always omitted. We describe an Open XML architecture at proof-of-concept which addresses these concerns. Compounds are identified through explicit connection tables or links to persistent Open resources such as PubChem. It is argued that if publishers adopt these tools and protocols, then the quality and quantity of chemical information available to bioscientists will increase and the authors, publishers and readers will find the process cost-effective.