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 (al ...

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 ...

in mathematical sciences from

Stanford University Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is consider ...

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 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. Universities typically offer both undergraduate and postgraduate programs. In the United States ...

; while a student, he also held internships at the

Xerox Palo Alto Research Center Xerox Holdings Corporation (; also known simply as Xerox) is an American corporation that sells print and digital document products and services in more than 160 countries. Xerox is headquartered in Norwalk, Connecticut (having moved from Sta ...

and

Stanford Linear Accelerator Center SLAC National Accelerator Laboratory, originally named the Stanford Linear Accelerator Center, is a United States Department of Energy National Laboratory operated by Stanford University under the programmatic direction of the U.S. Departme ...

. 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 Applied science, practical discipli ...

and

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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, Berkeley ...

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 conceptio ...

, and he was one of Charles Leiserson'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 mult ...

, 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 s ...

. He found an optimal solution for the two dimensional case of

Klee's measure problem In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of ( multidimensional) rectangular ranges can be computed. Here, a ''d''-dimensional rectangular range is defined to be a Cart ...

: given a set of ''n''

rectangle In Euclidean plane geometry, a rectangle is a quadrilateral with four right angles. It can also be defined as: an equiangular quadrilateral, since equiangular means that all of its angles are equal (360°/4 = 90°); or a parallelogram containi ...

s, 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 A shape or figure is a graphics, graphical representation of an obje ...

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 the ...

, 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 Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

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 ''Dr. Dobb's Journal'' (''DDJ'') was a monthly magazine published in the United States by UBM Technology Group, part of UBM. It covered topics aimed at computer programmers. When launched in 1976, DDJ was the first regular periodical focused on m ...

'' 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, continuous ...

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