2006 Jun 15 at 16:30
DC 1302
Kurt Mehlhorn, Max Planck Institute for Informatics, Saarbruecken, Germany
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 give 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. References [CGA] CGAL (Computational Geometry Algorithms Library). [FKMS05] S. Funke, Ch. Klein, K. Mehlhorn, and S. Schmitt. Controlled perturbation for Delaunay triangulations. SODA, pages 1047-1056, 2005. [HL04] D. Halperin and E. Leiserowitz. Controlled perturbation for arrangements of circles. International Journal of Computational Geometry and Applications, 14(4):277-310, 2004. preliminary version in SoCG 2003. [HR] D. Halperin and S. Raab. Controlled perturbation for arrangements of polyhedral surfaces with application to swept volumes. Available from Halperin's home page; a preliminary version appeared in SoCG 1999, pages 163-172. [HS98] Halperin and Shelton. A perturbation scheme for spherical arrangements with application to molecular modeling. CGTA: Computational Geometry: Theory and Applications, 10, 1998. [KMP+04] L. Kettner, K. Mehlhorn, S. Pion, S. Schirra, and C. Yap. Classroom examples of robustness problems in geometric computations. In ESA, volume 3221 of LNCS, pages 702-713, 2004. [MOS] K. Mehlhorn, R. Osbild, and M. Sagraloff. Reliable and Efficient Computational Geometry via Controlled Perturbation. to appear in ICALP 06.