Geometric Computing The Sciece of Making Geometric Algorithms Work
Prof. Kurt Mehlhorn ( MaxPlanckInstitut fur Informatik )

16:30 22nd September 2009Lecture Theartre B
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
RealRAM model of computation (as is numerical analysis); a RealRAM 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.