Accession Number : ADA313538
Title : Robust Proximity Queries in Implicit Voronoi Diagrams.
Descriptive Note : Technical rept.,
Corporate Author : BROWN UNIV PROVIDENCE RI DEPT OF COMPUTER SCIENCE
Personal Author(s) : Liotta, G. ; Preparata, F. P. ; Tamassia, R.
PDF Url : ADA313538
Report Date : MAY 1996
Pagination or Media Count : 35
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.
Descriptors : *ALGORITHMS, *COMPUTATIONS, *INTERROGATION, COMPUTER PROGRAMS, METHODOLOGY, INFORMATION TRANSFER, COSTS, GEOMETRY, LIBRARIES.
Subject Categories : Numerical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE