Jon Louis Bentley is a researcher in the field of computer science. He is credited with the invention of the k-d tree.

Bentley received a B.S. in mathematical sciences from Stanford University

Stanford University

The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...

 in 1974, and M.S. and Ph.D in 1976 from the University of North Carolina at Chapel Hill

University of North Carolina at Chapel Hill

The University of North Carolina at Chapel Hill is a public research university located in Chapel Hill, North Carolina, United States...

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

Stanford Linear Accelerator Center

The SLAC National Accelerator Laboratory, originally named 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...

. After receiving his Ph.D., he joined the faculty at Carnegie-Mellon University as an assistant professor of computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 and mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

. At CMU, his students included Brian Reid, John Ousterhout

John Ousterhout

John Kenneth Ousterhout is the chairman of Electric Cloud, Inc. and a professor of computer science at Stanford University. He founded Electric Cloud with John Graham-Cumming. Ousterhout previously was a professor of computer science at University of California, Berkeley where he created the Tcl...

, Jeff Eppinger

Jeff Eppinger

Jeffrey Lee Eppinger is a researcher, teacher, and entrepreneur in the field of computer science.Eppinger was a student at Carnegie Mellon University where he earned a Bachelor of Science in 1982, a Master of Science in 1987, and a PhD in Computer Science in 1988.His advisors were Alfred Spector...

, Joshua Bloch

Joshua Bloch

Joshua J. Bloch is a software engineer, currently employed at Google, and a technology author. He led the design and implementation of numerous Java platform features, including the Java Collections Framework, the java.math package, and the assert mechanism...

, and James Gosling

James Gosling

James A. Gosling, OC is a computer scientist, best known as the father of the Java programming language.-Education and career:In 1977, Gosling received a B.Sc in Computer Science from the University of Calgary...

, and he was one of Charles Leiserson

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

He found an optimal solution for the two dimensional case of Klee's measure problem

Klee's measure problem

In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of rectangular ranges can be computed...

: given a set of n rectangle

Rectangle

In Euclidean plane geometry, a rectangle is any quadrilateral with four right angles. The term "oblong" is occasionally used to refer to a non-square rectangle...

s, find the area of their union. He and Thomas Ottmann invented the Bentley–Ottmann algorithm, an efficient algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 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

Communications of the ACM is the flagship monthly journal of the Association for Computing Machinery . First published in 1957, CACM is sent to all ACM members, currently numbering about 80,000. The articles are intended for readers with backgrounds in all areas of computer science and information...

 magazine, and later collected the articles into two books of the same name. He has published or presented over 200 papers.

Bentley received the Dr. Dobb's

Dr. Dobb's Journal

Dr. Dobb's Journal was a monthly journal published in the United States by CMP Technology. It covered topics aimed at computer programmers. DDJ was the first regular periodical focused on microcomputer software, rather than hardware. It later became a monthly section within the periodical...

Excellence in Programming award in 2004.