Kurt Mehlhorn
Max Planck Institute for Informatics
Reliable and Efficient Geometric Computing
Abstract: Reliable implementation of geometric algorithms is a notoriously difficult task. In fact, most implementations (academic and commercial) of geometric algorithms fail on some input instances, i.e., crash or given an incorrect answer.
In the introductory part of the talk, we illustrate the pitfalls of geometric computing [KMP+04] and explain for one algorithm in detail where the problem lies and what goes wrong. In the main part of the talk, we discuss a recent approach to reliable and efficient geometric computing: controlled perturbation. The approach was introduced by D. Halperin and co-workers [HS98, HR, HL04] and redefined by us [MOS, FKMS05]. We show that the approach applies to a large class of geometric algorithms, in particular, most algorithms in CGAL, [CGA], and yields correct and efficient implementations. The method is easy to use.
