36571583
On Simultaneous Planar Graph Embeddings
We consider the problem of simultaneous embedding of planar graphs. There are two variants of this problem, one in which the mapping between the vertices of the two graphs is given and another in which the mapping is not given. In particular, given a mapping, we show how to embed two paths on an n ×n grid, and two caterpillar graphs on a 3n ×3n grid. We show that it is not always possible to simultaneously embed three paths. If the mapping is not given, we show that any number of outerplanar graphs can be embedded simultaneously on an O(n) ×O(n) grid, and an outerplanar and general planar graph can be embedded simultaneously on an O(n 2) ×O(n 2) grid.
57900050
Computational Geometry Column 42
A compendium of thirty previously published open problems in computational geometry is presented.
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.
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.
17480240
A compositional logic for protocol correctness
Abstract: We present a specialized protocol logic that is built around a process language for describing the actions of a protocol. In general terms, the relation between logic and protocol is like the relation between assertions in Floyd-Hoare logic and standard imperative programs. Like Floyd-Hoare logic, our logic contains axioms and inference rules for each of the main protocol actions and proofs are protocol-directed, meaning that the outline of a proof of correctness follows the sequence of actions in the protocol. We prove that the protocol logic is sound, in a specific sense: each provable assertion about an action or sequence of actions holds in any run of the protocol, under attack, in which the given actions occur. This approach lets us prove properties of protocols that hold in all runs, while explicitly reasoning only about the sequence of actions needed to achieve this property. In particular, no explicit reasoning about the potential actions of an attacker is required.
19578302
A lambda calculus of objects and method specialization
An untyped lambda calculus, extended with object primitives that reflect the capabilities of so-called delegation-based object-oriented languages, is presented. A type inference system allows static detection of errors, such as message not understood, while at the same time allowing the type of an inherited method to be specialized to the type of the inheriting object. Type soundness, in the form of a subject-reduction theorem, is proved, and examples illustrating the expressiveness of the pure calculus are presented.<<ETX>>
10705506
Linear logic proof games and optimization
§ 1. Introduction . Perhaps the most surprising recent development in complexity theory is the discovery that the class NP can be characterized using a form of randomized proof checker that only examines a constant number of bits of the “proof” that a string is in a language [6, 5, 31, 3, 4]. More specifically, writing ∣ x ∣ for the length of a string x , a language L in the class NP of languages recognizable in Nondeterministic polynomial time is traditionally given by a polynomial p and a polynomial-time predicate P such that a string x is in L iff there is some string y satisfying P (x, y), where ∣ y ∣ ≤ p (∣ x ∣). Intuitively, we can think of a string y as a possible proof that x ϵ L , with the predicate P some kind of proof checker that distinguishes good proofs from bad ones. A string x is therefore in a language L ϵ NP if there is a short proof that x ϵ L , and not in L otherwise. The surprising discovery is that the deterministic proof checker that reads the entire input and proof can be replaced by a probabilistic verifier that on input x and possible proof y , where y is presented in a certain way, flips at most O (log ∣ x ∣) coins and reads at most a constant number of bits of x and y . Obviously, a probabilistic verifier that does not read the whole proof will sometimes make mistakes. However, the surprising and essentially non-intuitive mathematical fact is that for each language L in NP, it is possible to find a polynomial q and verifier V flipping a logarithmic number of coins and reading a constant number of bits such that, for any x ϵ L , there exists y with ∣ y ∣ ≤ q(∣ x ∣) and with V (x, y) accepting with probability 1 and, for x ∉ L , there is no y with ∣ y ∣ ≤ q (∣ x ∣) and with V (x, y) accepting with probability ≥ 1/4. This idea canalsobeextended to PSPACE [10, 9], using a game that alternates between two players instead of a proof presented by a “single player.”
2495572
Adding type parameterization to the Java language
Although the Java programming language has achieved widespread acceptance, one feature that seems sorely missed is the ability to use type parameters (as in Ada generics, C++ templates, and ML polymorphic functions or data types) to allow a general concept to be instantiated to one or more specific types. In this paper, we propose parameterized classes and interfaces in which the type parameter may be constrained to either implement a given interface or extend a given class. This design allows the body of a parameterized class to refer to methods on objects of the parameter type, without introducing any new type relations into the language. We show that these Java extensions may be implemented by expanding parameterized classes at class load time, without any extension or modification to existing Java bytecode, verifier or bytecode interpreter.
30142201
The Implication Problem for Functional and Inclusion Dependencies
There are two implication problems for functional dependencies and inclusion dependencies: general implication and finite implication. Given a set of dependencies Σ ∪ { σ }, the problems are to determine whether σ holds in all databases satisfying Σ or all finite databases satisfying Σ . Contrary to the possibility suggested in Casanova, Fagin, and Papadimitriou (“Proceedings, 1st ACM Conf. on Principles of Database System,” pp. 171–176, 1982), there is a natural, complete axiom system for general implication. However, a simple observation shows that both implication problems are recursively unsolvable. It follows that there is no recursively enumerable set of axioms for finite implication.