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 Collect ...
, 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.htmlon
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