Geometric Computing The Sciece of Making Geometric Algorithms Work

Prof. Kurt Mehlhorn ( Max-Planck-Institut fur Informatik )

Computing with geometric objects (points, curves, and surfaces) is central for many engineering disciplines and lies at the heart of computer aided design systems. Implementing geometric algorithms is notoriously difficult and most actual implementations are incomplete: they are known to crash or deliver the wrong result on some instances. Geometric computing is based on the Real-RAM model of computation (as is numerical analysis); a Real-RAM is a machine equipped with real arithmetic. However, actual machines come with floating point arithmetic. In the introductory part of the talk, we illustrate the pitfalls of geometric computing and explain for one algorithm in detail where the problem lies and what can go wrong. In the main part of the talk I discuss approaches to reliable and efficient geometric computing, in particular, the exact computation paradigm and controlled perturbation. I report about recent theoretical advances (boolean operations for curved polygons, arrangements of curves in the plane and on surfaces, topological analysis of surfaces, real root isolation) and the use of the paradigms in systems LEDA and CGAL. The research combines techniques from computational geometry, solid modeling, computer algebra, and numerical analysis.