# Jon Bentley (computer scientist)

**Jon Louis Bentley** (born February 20, 1953) is an American computer scientist who is credited with the heuristic-based partitioning algorithm *k*-d tree.

Jon Bentley | |
---|---|

Born | Jon Louis Bentley February 20, 1953 Long Beach, California, ^{[1]} U.S. |

Alma mater | University of North Carolina at Chapel Hill Stanford University |

Title | Computer Scientist |

Scientific career | |

Thesis | Divide and conquer algorithms for closest point problems in multidimensional space (1976) |

Doctoral advisor | Donald Ford Stanat |

Doctoral students |

## Education and careerEdit

Bentley received a B.S. in mathematical sciences from Stanford University in 1974, and M.S. and Ph.D in 1976 from the University of North Carolina at Chapel Hill; while a student, he also held internships at the Xerox Palo Alto Research Center and Stanford Linear Accelerator Center.^{[1]} After receiving his Ph.D., he joined the faculty at Carnegie Mellon University as an assistant professor of computer science and mathematics.^{[1]} At CMU, his students included Brian Reid, John Ousterhout, Jeff Eppinger, Joshua Bloch, and James Gosling, and he was one of Charles Leiserson's advisors.^{[2]} Later, Bentley moved to Bell Laboratories, where he co-authored an optimized Quicksort algorithm with Doug McIlroy.^{[3]}

He found an optimal solution for the two dimensional case of Klee's measure problem: given a set of *n* rectangles, find the area of their union. He and Thomas Ottmann invented the Bentley–Ottmann algorithm, an efficient algorithm for finding all intersecting pairs among a collection of line segments. He wrote the *Programming Pearls* column for the *Communications of the ACM* magazine, and later collected the articles into two books of the same name.

Bentley received the *Dr. Dobb's* Excellence in Programming award in 2004.

## BibliographyEdit

*Programming Pearls*(2nd edition), ISBN 0-201-65788-0.*More Programming Pearls: Confessions of a Coder*, ISBN 0-201-11889-0.*Writing Efficient Programs*, ISBN 0-13-970244-X.*Divide and Conquer Algorithms in Multidimensional Space*, Ph.D. thesis.

## ReferencesEdit

- ^
^{a}^{b}^{c}Biography from Bentley, J. L.; Ottmann, T. A. (1979), "Algorithms for reporting and counting geometric intersections",*IEEE Transactions on Computers*,**C-28**(9): 643–647, doi:10.1109/TC.1979.1675432. **^**Jon Bentley at the Mathematics Genealogy Project**^**Jon L. Bentley; M. Douglas McIlroy (November 1993). "Engineering a sort function".*Software—Practice & Experience*.**23**(11).

## External linksEdit

- www.cs.bell-labs.com/cm/cs/pearls/code.html on GitHub
- Lucent Technologies press release (dead link)
- bug in Jon Bentley's binary search - google research
- The C Programming Language, both editions had shown the solution to the bug discussed in the above. In the second edition, it is in section 6.4 (Pointers to Structures).