Jack Snoeyink, UNC Chapel Hill
Geometric algorithms are usually developed in a model of computation that supports ideal, Euclidean points and lines, but are implemented using coordinates with limited precision. Much research has gone into simulating the ideal with limited precision; less has gone into exploring how the constraints of precision should affect algorithm design. A paper by Liotta, Preparata, and Tamassia from 1999 suggested "degree-driven algorithm design", and showed that, if you knew that all queries to a Voronoi diagram would be single precision, then you could essentially round the Voronoi itself to single precision to make a data structure that would answer proximity queries with double precision. (The minimum to represent Voronoi vertices is triple precision, which would lead to a naive bound of 6-fold precision required.) Unfortunately, they first needed to compute the Voronoi diagram, which required 4-fold precision. We show that triple precision is enough to compute a rounded structure directly, extending their work on degree-driven algorithm design.
(This is joint work with Dave Millman.)