20253449
Approximating Polygons and Subdivisions with Minimum Link Paths
We study several variations on one basic approach to the task of simplifying a plane polygon or subdivision: Fatten the given object and construct an approximation inside the fattened region. We investigate fattening by convolving the segments or vertices with disks and attempt to approximate objects with the minimum number of line segments, or with near the minimum, by using efficient greedy algorithms. We give some variants that have linear or O(n log n) algorithms approximating polygonal chains of n segments. We also show that approximating subdivisions and approximating with chains with. no self-intersections are NP-hard.
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.
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-
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.
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.
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.
1653333
A derivation system for security protocols and its logical formalization
Many authentication and key exchange protocols are built using an accepted set of standard concepts such as Diffie-Hellman key exchange, nonces to avoid replay, certificates from an accepted authority, and encrypted or signed messages. We introduce a basic framework for deriving security protocols from such simple components. As a case study, we examine the structure of a family of key exchange protocols that includes station-to-station (STS), ISO-9798-3, just fast keying (JFK), IKE and related protocols, deriving all members of the family from two basic protocols using a small set of refinements and protocol transformations. As initial steps toward associating logical derivations with protocol derivations, we extend a previous security protocol logic with preconditions and temporal assertions. Using this logic, we prove the security properties of the standard signature based challenge-response protocol and the Diffie-Hellman key exchange protocol. The ISO-9798-3 protocol is then proved correct by composing the correctness proofs of these two simple protocols.
3038947
Beyond proof-of-compliance: safety and availability analysis in trust management
Trust management is a form of distributed access control using distributed policy. statements. Since one party may delegate partial control to another party, it is natural to ask what permissions may be granted as the result of policy changes by other parties. We study security properties such as safety, and availability for a family of trust management languages, devising algorithms for deciding the possible consequences of certain changes in policy. While trust management is more powerful in certain ways than mechanisms in the access matrix model, and the security properties considered are more than simple safety, we find that in contrast to the classical HRU undecidability of safety properties, our primary security properties are decidable. In particular, most properties we studied are decidable in polynomial time. Containment, the most complicated security property we studied, is decidable in polynomial time for the simplest TM language in the family. The problem becomes co-NP-hard when intersection or linked roles are added to the language.
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.