A paradigm for robust geometric algorithms |
| |
Authors: | John E Hopcroft and Peter J Kahn |
| |
Affiliation: | (1) Department of Computer Science, Cornell University, 14853 Ithaca, NY, USA;(2) Department of Mathematics, Cornell University, 14853 Ithaca, NY, USA |
| |
Abstract: | 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. |
| |
Keywords: | Geometrical algorithm Algorithm Paradigm Correctness Convex Polyhedron Graph Stress |
本文献已被 SpringerLink 等数据库收录! |
|