# Speaker: Jenny Lam

##
Title: Computing Planar Voronoi Diagrams in Double Precision: A Further Example of Degree-driven Algorithm Design

##
Authors: David L. Millman, Jack Snoeyink

Abstract: Geometric algorithms use numerical computations to perform
geometric tests, so correct algorithms may produce erroneous results
if insufficient arithmetic precision is available. Liotta, Preparata,
and Tamassia, in 1999, suggested that algorithm design, which traditionally
considers running time and memory space, could also consider precision
as a resource. They demonstrated that the Voronoi diagram of n sites on
a U x U grid could be rounded to answer nearest neighbor queries on
the same grid using only double precision. They still had to compute
the Voronoi diagram before rounding, which requires the quadruple-precision
InCircle test. We develop a
"degree-2 Voronoi diagram" that can be computed using only double
precision by a randomized incremental construction in O(n log n log U)
expected time and O(n) expected space. Our diagram also answers nearest
neighbor queries, even though
it doesn't even use sufficient precision to determine a
Delaunay triangulation.