28965703
Classroom Examples of Robustness Problems in Geometric Computations
The algorithms of computational geometry are designed for a ma- chine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations to fail. Although this is well known, there is no comprehensive documentation of what can go wrong and why. In this extended abstract, we study a simple incremental algorithm for planar convex hulls and give examples which make the algorithm fail in all pos- sible ways. We also show how to construct failure-examples semi-systematically and discuss the geometry of the floating point implementation of the orientation predicate. We hope that our work will be useful for teaching computational ge- ometry. The full paper is available at www.mpi-sb.mpg.de/˜mehlhorn/ ftp/ClassRoomExamples.ps. It contains further examples, more theory, and color pictures. We strongly recommend to read the full paper instead of this extended abstract.
13864802
A Complete and Efficient Algorithm for the Intersection of a General and a Convex Polyhedron
A polyhedron is any set that can be obtained from the open halfspaces by a finite number of set complement and set intersection operations. We give an efficient and complete algorithm for intersecting two three-dimensional polyhedra, one of which is convex. The algorithm is efficient in the sense that its running time is bounded by the size of the inputs plus the size of the output times a logarithmic factor. The algorithm is complete in the sense that it can handle all inputs and requires no general position assumption. We also describe a novel data structure that can represent all three-dimensional polyhedra (the set of polyhedra representable by all previous data structures is not closed under the basic boolean operations).
12636571
Curve reconstruction: connecting dots with good reason
Curve reconstruction algorithms are supposed to reconstruct curves from point samples. Recent papers present algorithms that come with a guarantee: Given a sufficiently dense sample of a closed smooth curve, the algorithms construct the correct polygonal reconstruction. Nothing is claimed about the output of the algorithms, if the input is not a dense sample of a closed smooth curve, e.g., a sample of a curve with endpoints. We present an algorithm that comes with a guarantee for any setP of input points. The algorithm constructs a polygonal reconstruction G and a smooth curve that justifies G as the reconstruction fromP . © 2000 Elsevier Science B.V. All rights reserved.
41059566
On local routing of two-terminal nets
Abstract We examine the problem of finding edge-disjoint paths between pairs of vertices placed on inner as well as outer faces of a finite grid graph. For each path a global routing, which fixes the topology of the path relative to the nontrivial faces, is part of the input. We give necessary and sufficient conditions for the solvability of the problem and provide an algorithm to find a solution with running time quadratic in the size of the problem.
39971049
On Local Routing of Two-Terminal Nets
We showed that the local routing problem for two-terminal nets is solvable in quadratic time. There are three major open problems:
17694660
Resource Constrained Shortest Paths
The resource constrained shortest path problem (CSP) asks for the computation of a least cost path obeying a set of resource constraints. The problem is NP-complete. We give theoretical and experimental results for CSP. In the theoretical part we present the hull approach, a combinatorial algorithm for solving a linear programming relaxation and prove that it runs in polynomial time in the case of one resource. In the experimental part we compare the hull approach to previous methods for solving the LP relaxation and give an exact algorithm based on the hull approach. We also compare our exact algorithm to previous exact algorithms and approximation algorithms for the problem.
10770582
Polynomial and abstract subrecursive classes
We define polynomial time computable operator. Our definition generalizes Cook's definition to arbitrary function inputs. Polynomial classes are defined in terms of these operators; the properties of these classes are investigated. Honest polynomial classes are generated by running time. They posses a modified Ritchie-Cobham property. A polynomial class is a complexity class iff it is honest.
 Starting from the observation that many results about subrecursive classes hold for all reducibility relations (e.g. primitive recursive in, elementary recursive in), which were studied so far, we define abstract subrecursive reducibility relation. Many results hold for all abstract subrecursive reducibilities.