ACM Paris Kanellakis Theory and Practice Award
Max Planck Institute Germany – 2010

For contributions to algorithm engineering by creating the LEDA library for algorithmic problem solving.

Geometry is the mathematics of shape, size and distance. While geometry allows us to discover properties of objects at once both subtle and profound, its fundamental principles are remarkably simple.

The implementation of geometric algorithms is in contrast extremely complicated, and fraught with the problem of finding a compromise among precision, robustness, data organization and computational complexity. Understanding thoroughly this theory-practice chasm requires both deep knowledge and experience. The fundamental difficulty of implementing geometric algorithms for many years impeded progress in areas such as computer graphics, computer-aided geometric design, scientific computation, and computational biology.

In the late 1980s, Kurt Mehlhorn, who was already distinguished for his work in theoretical computer science,and his former student Stefan Näher, recognized the need to make available a robust, practical and efficient set of combinatorial and geometric algorithms and their underlying data structures. They developed the collection "Library of Efficient Data types and Algorithms," or "LEDA" for short.

The development of freely available algorithmic software deeply affected the work of thousands of researchers in many disciplines, and it has been incorporated into the product development of hundreds of companies. Some aspects of LEDA have also been incorporated into CGAL, a multi-institutional open-source applied geometry initiative. Today, LEDA continues to be developed and refined through a novel distribution model that is free to researchers and licensed to companies. Mehlhorn has also developed mathematical methods to certify both the theoretical and practical correctness of algorithms and their implementation. He has supervised numerous students and published several books on algorithms and algorithm engineering.

Germany – 1999

For important contributions in complexity theory and in the design, analysis, and practice of combinatorial and geometric algorithms.