Robustness in geometric algorithms

M.Sc. Thesis by Michael Neidhardt


The description of many geometric algorithms assumes that all arithmetic computations produce correct results. Naively implementing an algorithm with floating point-types exposes the program to rounding errors, which can lead to qualitative errors and program crashes. These are called robustness problems and several solutions exist. In this report I analyse a number of algorithms that solve the all-nearest-neighbors-problem and analyse a number of solutions to robustness problems, notably semi-static floating point filters and multiprecision types. The algorithms have been implemented with and without robust solutions. Benchmarks confirm the overall picture that robustness comes at a price, that filters are superior to multiprecision types, and that it is relatively hard to provoke this kind of error, meaning that it is often sufficient to use floating point calculations. The last fact makes filters attractive, in that they often use floating point-calculations as the first step.

The following files (all in Danish) are available for download: