2865065
A constant-factor approximation algorithm for optimal terrain guarding
We present the first constant-factor approximation algorithm for a non-trivial instance of the optimal guarding (coverage) problem in polygons. In particular, we give an O(1)-approximation algorithm for placing the fewest point guards on a 1.5D terrain, so that every point of the terrain is seen by at least one guard. While polylogarithmic-factor approximations follow from set cover results, our new results exploit geometric structure of terrains to obtain a substantially improved approximation algorithm.
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.
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.
57900050
Computational Geometry Column 42
A compendium of thirty previously published open problems in computational geometry is presented.
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>>
52847645
Standard ML-NJ Weak Polymorphism and Imperative Constructs
Standard ML of New Jersey (SML-NJ) uses weak-type variables to restrict the polymorphic use of functions that may allocate reference cells, manipulate continuations, or use exceptions. However, the type system used in the SML-NJ compiler has not been presented in a form other than source code and has not been proved correct. A type system, in the form of typing rules and an equivalent algorithm, that appears to subsume the implemented algorithm is presented. Both use type variables of only a slightly more general nature than the compiler. One insight in the analysis is that the indexed type of a free variable is used in two ways, once in describing the applicative behavior of the variable itself and once in describing the larger term containing the variable. Taking this into account, an application rule that is more general than SML-NJ is formulated for applications of polymorphic functions to imperative arguments. The soundness of the type system is proved for imperative code using operational semantics. >
31663632
MACiE: a database of enzyme reaction mechanisms
SUMMARY
MACiE (mechanism, annotation and classification in enzymes) is a publicly available web-based database, held in CMLReact (an XML application), that aims to help our understanding of the evolution of enzyme catalytic mechanisms and also to create a classification system which reflects the actual chemical mechanism (catalytic steps) of an enzyme reaction, not only the overall reaction.


AVAILABILITY
http://www-mitchell.ch.cam.ac.uk/macie/.
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
452980
On Abstraction and the Expressive Power of Programming Languages
We present a tentative theory of programming language expressiveness based on reductions (language translations) that preserve observational equivalence. These are called “abstraction-preserving” because of a connection with a definition of “abstraction” or “information-hiding” mechanism. If there is an abstraction-preserving reduction from one language to another, then essentially every function on natural numbers that is definable in the first is also definable in the second. Moreover, regardless of the set of first-order functions definable in either language, no programming language with an abstraction mechanism can be reduced to a language without. Since Lisp with user-defined special forms does not have an abstraction mechanism, it is therefore not “universal” in this theory, in spite of the ability to define every partial recursive function on the natural numbers. Several examples and counter-examples to abstraction-preserving reductions are given. We do not know whether there is a natural universal language with respect to abstraction-preserving reduction.