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
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE