Jon Bentley (Informatiker)

Jon Louis Bentley (* 20. Februar 1953 in Long Beach (Kalifornien)) ist ein US-amerikanischer Informatiker. Er ist bekannt für die Entwicklung einiger Algorithmen und Bücher über Algorithmen, die aus seiner Kolumne Programming Pearls in der Zeitschrift Communications of the ACM entstanden.

Bentley studierte Mathematik an der Stanford University mit dem Bachelor-Abschluss 1974, erhielt seinen Master-Abschluss 1976 an der University of North Carolina at Chapel Hill, an der er 1976 bei Donald Stanat promoviert wurde (Divide and Conquer Algorithms for Closest Point Problems in Multidimensional Space). Anfang der 1980er Jahre war er Assistant Professor an der Carnegie Mellon University und später bei den Bell Laboratories.

Von Bentley stammt der k-d-Baum. Mit Thomas Ottmann entwickelte er 1979 einen Algorithmus zur Bestimmung der Schnittpunkte einer Menge von Liniensegmenten. 1977 fand er einen Algorithmus für die zweidimensionale Verallgemeinerung des Maßproblems von Victor Klee (man finde den Flächeninhalt einer Menge von n Rechtecken, Klee stellte die Frage für eine Menge von n Liniensegmenten und beide fanden Algorithmen mit Laufzeit der Größenordnung $n\,\log(n)$) 1999 fand er mit Douglas McIlroy den VCDIFF Algorithmus.

2004 erhielt er den Excellence in Programming Award von Dr. Dobbs.

Schriften

• Programming Pearls, ACM Press 1986, Addison-Wesley, 2. Auflage 1999, ISBN 0-201-65788-0.
• More Programming Pearls: Confessions of a Coder, Addison-Wesley, 1988, ISBN 0-201-11889-0.
• Writing Efficient Programs, Prentice-Hall 1982, ISBN 0-13-970244-X.