Jon Bentley (computer scientist)
Jon Bentley | |
|---|---|
| Born | Jon Louis Bentley February 20, 1953 |
| Alma mater | University of North Carolina at Chapel Hill Stanford University |
| Occupation | Computer scientist |
| Employer | Avaya |
| 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 | |
Jon Louis Bentley (born February 20, 1953) is an American computer scientist who is credited with the heuristic-based partitioning algorithm k-d tree.
Education and career
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.
Bibliography
- 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.
References
- ^ 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 links
- 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).
