# Jon Bentley

American computer scientist

## Jon Bentley 's AcademicInfluence.com Rankings

## Download Badge

Computer Science

## Jon Bentley 's Degrees

- PhD Computer Science University of North Carolina at Chapel Hill
- Masters Computer Science Stanford University
- Bachelors Mathematics University of Richmond

## Similar Degrees You Can Earn

## Why Is Jon Bentley Influential?

(Suggest an Edit or Addition)According to Wikipedia, Jon Louis Bentley 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 PhD 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. After receiving his Ph.D., he joined the faculty at Carnegie Mellon University as an assistant professor of computer science and mathematics. 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. Later, Bentley moved to Bell Laboratories, where he co-authored an optimized Quicksort algorithm with Doug McIlroy.

## Jon Bentley 's Published Works

### Published Works

- Multidimensional binary search trees used for associative searching (1975) (7113)
- An Algorithm for Finding Best Matches in Logarithmic Expected Time (1976) (3087)
- Quad trees a data structure for retrieval on composite keys (1974) (1788)
- Algorithms for Reporting and Counting Geometric Intersections (1979) (1054)
- Multidimensional divide-and-conquer (1980) (703)
- Data Structures for Range Searching (1979) (658)
- A locally adaptive data compression scheme (1986) (574)
- Scaling and related techniques for geometry problems (1984) (527)
- Programming pearls (1987) (500)
- Multidimensional Binary Search Trees in Database Applications (1979) (458)
- Fast algorithms for sorting and searching strings (1997) (440)
- K-d trees for semidynamic point sets (1990) (410)
- Decomposable Searching Problems I: Static-to-Dynamic Transformation (1980) (405)
- On the Average Number of Maxima in a Set of Vectors and Applications (1978) (398)
- Decomposable Searching Problems (1979) (361)
- Optimal Expected-Time Algorithms for Closest Point Problems (1980) (343)
- An Almost Optimal Algorithm for Unbounded Searching (1976) (307)
- Programming pearls: little languages (1986) (275)
- An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles (1980) (250)
- Programming pearls: algorithm design techniques (1984) (245)
- Engineering a sort function (1993) (210)
- Efficient worst-case data structures for range searching (1978) (185)
- Divide-and-conquer in multidimensional space (1976) (170)
- Amortized analyses of self-organizing sequential search heuristics (1985) (157)
- Writing efficient programs (1982) (146)
- Fast linear expected-time algorithms for computing maxima and convex hulls (1993) (134)
- Experiments on traveling salesman heuristics (1990) (134)
- Divide and Conquer for Linear Expected Time (1978) (121)
- Approximation algorithms for convex hulls (1982) (117)
- Fast Algorithms for Constructing Minimal Spanning Trees in Coordinate Spaces (1978) (116)
- The Complexity of Finding Fixed-Radius Near Neighbors (1977) (115)
- A general method for solving divide-and-conquer recurrences (1980) (95)
- A tree machine for searching problems (1979) (81)
- A Parallel Algorithm for Constructing Minimum Spanning Trees (1980) (76)
- Implicit CAPTCHAs (2005) (73)
- Analysis of Range Searches in Quad Trees (1975) (72)
- More programming pearls - confessions of a coder (1988) (72)
- Programming pearls: perspective on performance (1984) (71)
- Data compression using long common strings (1999) (71)
- A survey of techniques for fixed radius near neighbor searching. (1975) (68)
- Programming pearls: a literate program (1986) (57)
- A Problem in Multivariate Statistics: Algorithm, Data Structure and Applications. (1978) (56)
- Programming pearls: literate programming (1986) (54)
- A Note on Euclidean Near Neighbor Searching in the Plane (1979) (45)
- Programming pearls (2nd ed.) (1999) (44)
- A system for algorithm animation tutorial and user manual (1990) (41)
- Programming pearls: a sample of brilliance (1987) (36)
- The Complexity of Manipulating Hierarchically Defined Sets of Rectangles (1981) (35)
- Transforming static data structures to dynamic structures (1979) (35)
- Programming pearls: a spelling checker (1985) (32)
- Worst-Case Analyses of Self-Organizing Sequential Search Heuristics. (1983) (32)
- A survey of algorithms and data structures for range searching (1978) (30)
- Call Center Customer Verification by Query-Directed Passwords (2004) (29)
- A Worst-Case Analysis of Nearest Neighbor Searching by Projection (1980) (29)
- GRAP—a language for typesetting graphs (1986) (29)
- CAPTCHA Challenge Tradeoffs: Familiarity of Strings versus Degradation of Images (2006) (29)
- Divide and conquer algorithms for closest point problems in multidimensional space. (1976) (27)
- Statistics on VLSI Designs. (1980) (26)
- Data compression with long repeated strings (2001) (26)
- The NAG library ‘machine’ (1979) (25)
- Programming pearls: how to sort (1984) (23)
- CAPTCHA challenge strings: problems and improvements (2006) (21)
- Generating Sorted Lists of Random Numbers (1980) (20)
- Heuristics for Partial-Match Retrieval Data Base Design (1976) (19)
- How Much Assurance Does a PIN Provide? (2005) (18)
- Chem - a program for phototypesetting chemical structure diagrams (1987) (17)
- Query-directed passwords (2005) (17)
- Programming pearls: Document design (1986) (16)
- Algorithms on vector sets (1979) (15)
- Programming pearls: data structures programs (1983) (15)
- Tools for Printing Indexes (1989) (15)
- An Alphard Specification of a Correct and Efficient Transformation on Data Structures (1980) (14)
- A general class of resource tradeoffs (1980) (14)
- A System for Algorithm Animation (1991) (13)
- Two papers on a tree-structured parallel computer (1979) (13)
- Programming pearls: thanks, heaps (1985) (13)
- Programmimg pearls (1985) (11)
- Programming pearls: Writing correct programs (1983) (11)
- An introduction to algorithm design (1978) (10)
- The Power of a One-Dimensional Vector of Processors (1980) (10)
- Algorithm Design Techniques (1984) (9)
- Writing efficient code (1981) (9)
- A Case Study in Applied Algorithm Design (1984) (9)
- Grap— a language for typesetting graphs. Tutorial and user manual (1990) (9)
- Programming pearls: self-describing data (1987) (8)
- Programming pearls: the envelope is back (1986) (8)
- Exercises in Software Design (1987) (7)
- Programming Perls (1984) (6)
- Programming pearls: Aha algorithms (1983) (6)
- SORTING STRINGS WITH THREE-WAY RADIX QUICKSORT (1998) (6)
- Programming pearls: Cracking the oyster (1983) (6)
- Programming pearls: little program, a lot of fun (1984) (5)
- In the realm of insight and creativity (2008) (5)
- Programming pearls: profilers (1987) (5)
- Programming pearls: the back of the envelope (1984) (5)
- How to Sort (1984) (4)
- Programming pearls: birth of a cruncher (1986) (4)
- A Randomized Data Structure for Ordered Sets (1989) (4)
- On the Enhancement of Portability within the NAG Project - Statistical Survey (1976) (4)
- Programming pearls: graphic output (1984) (4)
- Template-driven interfaces for numerical subroutines (1993) (4)
- Programming pearls: associative arrays (1985) (4)
- Special Feature An Introduction to Algorithm Design (1979) (4)
- Two papers on range searching (1978) (3)
- Programming pearls: tricks of the trade (1985) (3)
- Transforming Static Data Structures to Dynamic Structures (Abridged Version) (1979) (3)
- Programming pearls: squeezing space (1984) (3)
- Little languages for pictures in AWK (1989) (3)
- A Case Study in Writing Efficient Programs. (1983) (2)
- Teaching the Tricks of the Trade (1988) (2)
- Programming pearls: confessions of a coder (1985) (2)
- Bumper-Sticker Computer Science (1985) (2)
- Algorithms for multivariate nonparametrics (1978) (2)
- Programming pearls: the Furbelow memorandum (1987) (2)
- Preparing the NAG library (1980) (1)
- Probabilistic Analysis of Algorithms (1982) (1)
- Analyzing and Improving Challenge Strings for CAPTCHAs (2006) (1)
- Tiny Experiments for Algorithms and Life (2006) (1)
- Using Information Extraction for Quality Analysis in Human Authentication (2005) (1)
- Working smarter: 3 prescriptions for productivity (1988) (1)
- Algorithm Design Techniques -- Programming Pearls (1984) (1)
- Programming pearls: selection (1985) (1)
- Self-Organizing Sequential Search Heuristics (1999) (1)
- Excerpt from Programming Pearls: The Back of the Envelope (1999) (1)
- The Furbelow Memorandum (1987) (0)
- Efficiency Considerations for C Programs on a VAX (Trademark) 11/780. (1982) (0)
- AN ALMOST OPTIMAL ALGORTTHM FOR UNBOUNDED SIZARCHING (1975) (0)
- Squeezing Space (1984) (0)
- Lecture 2 : Fixed-Radius Near Neighbors and Geometric Basics (0)
- 3.1.1 Triangulating a Monotone Polygon 3.2 Range Minima 2.3.2 Query Retrieval 3.1 All Nearest Smaller Values 2.2 Preex Minima and All Nearest Smaller Values (1998) (0)
- Programming pearls: cutting the Gordian knot (1986) (0)
- DIVIDE AND CONQUER FOR LLYEAR EMECFED TIME * (1978) (0)
- Lower Bounds for Constant Depth Circuits for Preex Problems, in Proc. of 10th International 5. Conclusion and Open Problems (1992) (0)
- A Little Program, A Lot of Fun (1984) (0)
- Literate Programming (1986) (0)
- Data Structures A Locally Adaptive Data (1986) (0)
- Code Tuning -- Programming Pearls (1984) (0)
- Applications of Statistics to Applied Algorithm Design (1981) (0)
- Programming pearls: updates (1984) (0)
- A General Class of Resource Tradeoffs (Extended Abstract) (1980) (0)
- Code Tuning (1984) (0)
- Exercises in software engineering (1987) (0)
- Learning from Experience: 11178 (2007) (0)
- By Jon Bentley WRITING CORRECT PROGRAMS (1999) (0)
- ANALYSIS OF ALGORITHMS (1999) (0)
- 7. Acknowledgments 8. References 6. Concluding Remarks (1981) (0)
- Experiments for Algorithm Engineering (2003) (0)
- Optimal Circuit Clustering for Delay Minimization Under a More General Delay Model (2003) (0)
- CODE TUNING IN CONTEXT (1999) (0)
- Software Explorations THE BIG SQUEEZE (0)
- Introduction to systolic algorithms and architectures (1983) (0)
- Selecting Data for Experiments: Past, Present and Future (2014) (0)
- Options for spoken human-computer authentication in mobile environments (2008) (0)
- 5. Conclusion and Open Problems Step 4.3 for Each Internal Node Build Tablem , 1 for Array M in M , Level of the Tree Number of Children per Node (0)
- Back-of-the-envelope estimating (1987) (0)

This paper list is powered by the following services:

## Other Resources About Jon Bentley

## What Schools Are Affiliated With Jon Bentley ?

Jon Bentley is affiliated with the following schools: