A paradigm for robust geometric algorithms

This paper explores a paradigm for producing geometrical algorithms in which logical decisions that depend on finite-precision numerical calculation cannot lead to failure. It applies this paradigm to the task of intersecting two convex polyhedral objects. A key tool in this work is a method of perturbing embedding polyhedra in ways consistent with their topology.Work on this paper was supported in part by NSF Grant DMC-86-17355, NSF Grant DMS-87-02070, ONR Grant N00014-86-0281, ONR Grant N00014-88-0591, and the U.S. Army Research Office through MSI, Cornell University.