A Paradigm for Robust Geometric Algorithms
Abstract
Geometrical algorithms in use in computer aided design systems today often fail for numerical reasons. The cause of these failures usually can be traced to logical decisions such as branch on zero that depend on the results of numerical calculations. Numerical inaccuracies, introduced either in the initial data or in the finite-precision arithmetic that is used, may result in a set of logical decisions that are inconsistent. This loss of logical consistency usually proves fatal to the algorithm. Our interest is in geometric algorithms that are robust in the sense that they are provably immune to such potential problems. This paper explores a paradigm that should have wide applicability for producing robust algorithms, and it applies the paradigm to the task of intersecting two convex polyhedral objects. The paradigm was previously used in an implementation of an algorithm for intersecting polyhedral objects that was substantially more robust than algorithms implemented earlier. This paper is a first step in developing a mathematical framework that justifies the underlying ideas in this implementation. In particular, an important tool in this work is a method of manipulating embedded polyhedra in ways consistent with their topology. (kr)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1989
- Accession Number
- ADA214324
Entities
People
- John E. Hopcroft
- Peter J. Kahn
Organizations
- Cornell University