# Kurt Mehlhorn

Kurt Mehlhorn (né le 29 août 1949 à Ingolstadt) est un chercheur en informatique allemand, connu pour ses travaux en algorithmique, géométrie algorithmique, théorie de la complexité , complexité de la communication et algorithmique des graphes. Il a contribué considérablement au développement de l'informatique universitaire en Allemagne, notamment par la création de l'Institut Max-Planck d'informatique (MPII) à Sarrebruck dont il est l'un des directeurs, et par une activité de recherche et de direction de recherche soutenues.

## Biographie

Après des études d'informatique et de mathématiques à l'université technique de Munich de 1968 à 1971, il part à l'université Cornell de 1971 à 1974 sur une bourse de la Studienstiftung des deutschen Volkes ; il obtient un Ph. D. en 1974 sous la direction de Robert L. Constable avec une thèse intitulée « Polynomial and Abstract Subrecursive Classes ». Depuis 1975, il est à l'université de la Sarre à Sarrebruck en Allemagne. De 1976 à 1978 et à nouveau de 1987 à 1989, il dirige le département d'informatique. Depuis 1990, il est directeur de l'Institut Max-Planck d'informatique (MPII), aussi à Sarrebruck.

## Travaux

Mehlhorn est l'auteur de plusieurs livres. Chercheur prolifique, et est de plus auteur ou coauteur de plus de 250 publications scientifiques avec plus de 250 coauteurs. Il a apporté des contributions fondamentales sur les structures de données, la géométrie algorithmique, le calcul formel, le calcul parallèle, technologie VLSI, et théorie de la complexité, combinatorial optimization, et algorithmique des graphes. Il est une figure importante dans le développement de la conception et l’analyse des algorithmes, leur implémentation et optimisation. Il a aussi co-écrit l'un des articles fondateurs sur la complexité de la communication.
Il est aussi connu pour la création avec Stefan Näher de LEDA (Library of Efficient Data types and Algorithms (en)), une librairie de structure de données et d'algorithmes. Cette bibliothèque est reconnue pour ses algorithmes très efficaces et robustes du point de vue théorique, et sa bonne implémentation. Il a créé, avec Stefan Näher et Christian Uhrig, une entreprise appelée Algorithmic Solutions GmbH en 1995.
Mehlhorn a joué un rôle important dans la création de plusieurs centres de recherche en informatique en Allemagne. Il était la force motrice dans la création de l'Institut Max-Planck d'informatique (MPII). Mehlhorn est l'un des initiateurs du centre d'informatique Leibniz-Zentrum für Informatik à Dagstuhl. Avec Max Fontet, il a initié la série de colloques Symposium on Theoretical Aspects in Computer Science (STACS) et il est à l'origine du European Symposium on Algorithms. Mehlhorn assume ou a assumé un nombre important dee resposabilités dans la gestion académique de la recherche, comme membre de conseils d'administration, conseils scientifiques et autres organes de direction, en Allemagne, en niveau européen et aux États-Unis. Ainsi, il est ou a été administrateur du International Computer Science Institute (en) à Berkeley, et membre du conseil d'administration de l'Université Jacobs de Brême, membre du sénat de la Deutsche Forschungsgemeinschaft, président du conseil scientifique de l'INRIA, où il succède à Martin Wirsing.
Mehlhorn a dirigé ou codirigé 84 thèses et a près de 230 descendants académiques. Parmi ses élèves, il y a Susanne Albers, Helmut Alt, Hannah Bast, Rudolf Fleischer, Michael Kaufmann, Hans-Peter Lenhof, Athanasios Tsakalidis. Une Festschrift a été publiée en son honneur à l’occasion de son 60e anniversaire.

## Prix et distinctions
### Prix

* 1987 : Prix Gottfried Wilhelm Leibniz avec Günter Hotz et Wolfgang Paul (de).
* 1989 : Prix Gay-Lussac Humboldt
* 1994 : Prix Karl-Heinz-Beckurts
* 1995 : Médaille Konrad-Zuse
* 2010 : Prix de l'EATCS, pour ses travaux en informatique théorique et son investissement dans la communauté scientifique, notamment son rôle clé dans la création de l'Institut Max-Planck d'informatique et de la conférence ESA (European Symposium on Algorithms)
* 2010 : Prix Paris Kanellakis pour la création de LEDA
* 2013 : Prix international Khwarizmi (en)
* 2014 : Médaille Erasmus de l'Academia Europaea.

### Sociétés savantes

* 1995 : membre de l'Academia Europaea
* 1999 : Fellow de l’Association for Computing Machinery.
* 2001 : membre de l'Académie des sciences de Berlin-Brandebourg
* 2004 : membre de l'Académie des sciences Leopoldina
* 2014 : membre étranger de l'Académie nationale d'ingénierie des États-Unis
* 2014 : membre étranger de l'Indian National Academy of Engineering (en)
* 2015 : associé étranger de l'Académie nationale des sciences (États-Unis).
* 2016 : Fellow de l'EATCS

### Docteur honoris causa

* 2002 : Université Otto von Guericke de Magdebourg
* 2006 : Université de Waterloo
* 2008 : Université d'Aarhus
* 2014 : Université de Göteborg

## Publications
### Livres

* Kurt Mehlhorn, Effiziente Algorithmen, Stuttgart, Teubner, 1977. Édition révisée et traduite en anglais sous le titre Data Structures and Algorithms, Springer-Verlag, 1984.
* Kurt Mehlhorn, Data Structures and Algorithms II : Graph Algorithms and NP-completeness, Springer-Verlag, 1984.
* Kurt Mehlhorn, Data Structures and Algorithms III : Multidimensional Searching and Computational Geometry, Springer-Verlag, 1984.
* Jacques Loeckx, Kurt Mehlhorn et Reinhard Wilhelm, Foundations of Programming Languages, J. Wiley, 1988, 426 p. (ISBN 0-471-92139-4).
* (en) Kurt Mehlhorn et Stefan Näher, LEDA : a platform for combinatorial and geometric computing, Cambridge, Cambridge University Press, 1999, 1018 p. (ISBN 978-0-521-56329-1, lire en ligne).
* Kurt Mehlhorn et Peter Sanders, Algorithms and Data Structures : The Basic Toolbox, Springer, 2008, 300 p. (ISBN 978-3-540-77977-3, lire en ligne).

### Articles (sélection)

* Kurt Mehlhorn et Erik M. Schmidt, « Las Vegas is better than determinism in VLSI and distributed computing », Proc. 14th ACM Symp. Theory of Computing (STOC),‎ 1982, p. 330–337 (DOI 10.1145/800070.802208).
* Kurt Mehlhorn et Uzi Vishkin, « Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories », Acta Informatica, vol. 21, n$^o$ 4,‎ 1984, p. 339–374 (DOI 10.1007/BF00264615).
* Helmut Alt, Kurt Mehlhorn, Hubert Wagener et Emo Welzl, « Congruence, similarity, and symmetries of geometric objects », Discrete and Computational Geometry, vol. 3, n$^o$ 1,‎ 1988, p. 237–256 (DOI 10.1007/BF02187910).
* Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin et Robert E. Tarjan, « Faster algorithms for the shortest path problem », Journal of the Association for Computing Machinery, vol. 37, n$^o$ 2,‎ 1990, p. 213–223 (DOI 10.1145/77600.77615).
* Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert et Robert E. Tarjan, « Dynamic perfect hashing: upper and lower bounds », SIAM Journal on Computing, vol. 23, n$^o$ 4,‎ 1994, p. 738–761 (DOI 10.1137/S0097539791194094).
* Michael Sagraloff et Kurt Mehlhorn, « Computing real roots of real polynomials », Journal of Symbolic Computation, vol. 73,‎ 2016, p. 46-86 (DOI 10.1016/j.jsc.2015.03.004).