Date: 17 Dec 2008 From: jyrki@diku.dk Subject: Oral defence of M.Sc. thesis Oral defence of M.Sc. thesis: Robustness in geometric algorithms Defender: Michael Neidhardt Censor: Anders Heyden Supervisor: Jyrki Katajainen Time: Thursday, 18 December 2008, 14.00–15.00 Place: SP25, Universitetsparken 1 The defence will be held in Danish. Abstract: 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-neighbours problem and analyse a number of solutions to robustness problems, notably semi-static floating-point filters and multi-precision types. The algorithms have been implemented with and without robust subroutines. Benchmarks confirm the overall picture that robustness comes at a price, that filters are superior to multi-precision 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. PE-lab's home page: http://www.diku.dk/~jyrki/PE-lab/