Robust Proximity Queries in Implicit Voronoi Diagrams.
Abstract
In the context of methodologies intended to confer robustness to geometric algorithms, we elaborate on the exact computation paradigm and formalize the notion of degree of a geometric algorithm, as a worst-case quantification of the precision (number of bits) to which arithmetic calculation have to be executed in order to guarantee topological correctness. We also propose a formalism for the expeditious evaluation of algorithmic degree. As an application of this paradigm and an illustration of our general approach, we consider the important classical problem of proximity queries in 2 and 3 dimensions, and develop a new technique for the efficient and robust execution of such queries based on an implicit representation of Voronoi diagrams. Our new technique gives both low degree and fast query time, and for 2D queries is optimal with respect to both cost measures of the paradigm, asymptotic number of operations and arithmetic degree.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1996
- Accession Number
- ADA313538
Entities
People
- F. P. Preparata
- G. Liotta
- R. Tamassia
Organizations
- Brown University