Jon Louis Bentley (born February 20, 1953) is an American

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus ( ...

who is credited with the heuristic-based partitioning algorithm ''k''-d tree.

Education and career

Bentley received a

B.S. A Bachelor of Science (BS, BSc, SB, or ScB; from the Latin ') is a bachelor's degree awarded for programs that generally last three to five years. The first university to admit a student to the degree of Bachelor of Science was the University of ...

in mathematical sciences from Stanford University in 1974, and

M.S. A Master of Science ( la, Magisterii Scientiae; abbreviated MS, M.S., MSc, M.Sc., SM, S.M., ScM or Sc.M.) is a master's degree in the field of science awarded by universities in many countries or a person holding such a degree. In contrast to ...

and

PhD PHD or PhD may refer to: * Doctor of Philosophy (PhD), an academic qualification Entertainment * '' PhD: Phantasy Degree'', a Korean comic series * ''Piled Higher and Deeper ''Piled Higher and Deeper'' (also known as ''PhD Comics''), is a newsp ...

in 1976 from the

University of North Carolina at Chapel Hill A university () is an institution of higher (or tertiary) education and research which awards academic degrees in several academic disciplines. ''University'' is derived from the Latin phrase ''universitas magistrorum et scholarium'', which r ...

; while a student, he also held internships at the Xerox Palo Alto Research Center and

Stanford Linear Accelerator Center SLAC National Accelerator Laboratory, originally named the Stanford Linear Accelerator Center, is a United States Department of Energy National Laboratories, United States Department of Energy National Laboratory operated by Stanford Univers ...

. After receiving his Ph.D., he joined the faculty at

Carnegie Mellon University Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...

as an assistant professor of

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

and mathematics. At CMU, his students included Brian Reid,

John Ousterhout John Kenneth Ousterhout (, born October 15, 1954) is a professor of computer science at Stanford University. He founded Electric Cloud with John Graham-Cumming. Ousterhout was a professor of computer science at University of California, Berk ...

Jeff Eppinger Jeffrey Lee Eppinger (born ca 1960) is an American computer scientist, entrepreneur and Professor of the Practice at the Carnegie Mellon University, School of Computer Science, Institute for Software Research. Eppinger was a student at Carnegie Me ...

Joshua Bloch Joshua J. Bloch (born August 28, 1961) is an American software engineer and a technology author, formerly employed at Sun Microsystems and Google. He led the design and implementation of numerous Java platform features, including the Java Collec ...

, and

James Gosling James Gosling (born May 19, 1955) is a Canadian computer scientist, best known as the founder and lead designer behind the Java programming language. Gosling was elected a member of the National Academy of Engineering in 2004 for the conception ...

, and he was one of

Charles Leiserson Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof. As part of this effort, he developed the Cilk multithreaded language. ...

's advisors. Later, Bentley moved to

Bell Laboratories Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984), then AT&T Bell Laboratories (1984–1996) and Bell Labs Innovations (1996–2007), is an American industrial research and scientific development company owned by mul ...

, where he co-authored an optimized

Quicksort Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...

algorithm with

Doug McIlroy Malcolm Douglas McIlroy (born 1932) is a mathematician, engineer, and programmer. As of 2019 he is an Adjunct Professor of Computer Science at Dartmouth College. McIlroy is best known for having originally proposed Unix pipelines and developed se ...

. He found an optimal solution for the two dimensional case of Klee's measure problem: given a set of ''n'' rectangles, find the

area Area is the quantity that expresses the extent of a region on the plane or on a curved surface. The area of a plane region or ''plane area'' refers to the area of a shape or planar lamina, while ''surface area'' refers to the area of an open su ...

of their union. He and Thomas Ottmann invented the

Bentley–Ottmann algorithm In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all ''crossings'' in a set of line segments, i.e. it finds the ''intersection points'' (or, simply, ''intersections'') of line segments. It extends th ...

, an efficient

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

for finding all intersecting pairs among a collection of line segments. He wrote the ''Programming Pearls'' column for the ''

Communications of the ACM ''Communications of the ACM'' is the monthly journal of the Association for Computing Machinery (ACM). It was established in 1958, with Saul Rosen as its first managing editor. It is sent to all ACM members. Articles are intended for readers with ...

'' 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), . * ''More Programming Pearls: Confessions of a Coder'', . * ''Writing Efficient Programs'', . * ''Divide and Conquer Algorithms in Multidimensional Space'', Ph.D. thesis.

References

External links

www.cs.bell-labs.com/cm/cs/pearls/code.html
on

GitHub GitHub, Inc. () is an Internet hosting service for software development and version control using Git. It provides the distributed version control of Git plus access control, bug tracking, software feature requests, task management, co ...

Lucent Technologies press release

- google research **

The C Programming Language ''The C Programming Language'' (sometimes termed ''K&R'', after its authors' initials) is a computer programming book written by Brian Kernighan and Dennis Ritchie, the latter of whom originally designed and implemented the language, as well as ...

, 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). {{DEFAULTSORT:Bentley, Jon 1953 births Living people American computer scientists American computer programmers Researchers in geometric algorithms Carnegie Mellon University faculty Stanford University School of Humanities and Sciences alumni University of North Carolina at Chapel Hill alumni People from Long Beach, California