Degree-Driven Design of Geometric Algorithms for Point Location, Proximity, and Volume Calculation

October 31, 2012

Correct implementation of published geometric algorithms is surprisingly
difficult. Geometric algorithms are often designed for Real-RAM, a
computational model that provides arbitrary precision arithmetic operations at
unit cost. Commodity hardware provides only finite precision and may result in
arithmetic errors. While the errors may seem small, if ignored, they may cause
incorrect branching, which may cause an implementation to reach an undefined
state, produce erroneous output, or crash. In 1999 Liotta, Preparata and
Tamassia proposed that in addition to considering the resources of time and
space, an algorithm designer could also consider the arithmetic precision
necessary to guarantee a correct implementation. They called this design
technique degree-driven algorithm design. By considering the time, space,
and precision for a problem at the design stage we arrive at new solutions, gain
further insight, and find simpler representations. In this talk, I describe how
degree-driven design supports the development of new and robust geometric
algorithms.