Kurt Mehlhorn

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.

Quick Links

2012-2013 DLS

  • Zvi Galil
  • Hector Levesque
  • Jennifer Chayes
  • Renée Miller
  • Maneesh Agrawala
  • David Eppstein

2011-2012 DLS

  • Bruno Buchberger
  • Saul Greenberg
  • Ed Lazowska
  • Jeannette Wing
  • Cynthia Dwork

2010-2011 DLS

  • Stuart Feldman
  • Madhu Sudan
  • Susan Landau
  • Gilles Brassard
  • Joe Marks
  • Jon Kleinberg

2009-2010 DLS

  • Andy Yao
  • Paul Van Oorschot
  • Shafi Goldwasser
  • Adi Shamir
  • Fran Allen

2008-2009 DLS

  • Alan Kay
  • Eric Brewer
  • Anne Condon
  • Nancy Leveson
  • Tom Furness

2007-2008 DLS

  • David Patterson
  • Manuela Veloso
  • David D. Clark
  • Christos Papadimitriou

2006-2007 DLS

  • Kurt Mehlhorn
  • Ben Shneiderman
  • Barbara Liskov
  • Vint Cerf

2005-2006 DLS

  • Umesh Vazirani
  • Stephen Cook
  • Andrew Tanenbaum
  • Andries van Dam

2004-2005 DLS

  • Alfred Aho
  • Brian Kernighan
  • Jim Gray
  • Barbara Grosz
  • Jim Mitchell