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.