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/