At this time he developed his most cited work, the heuristic-based partitioning algorithm k-d tree, published in 1975.

[1] 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.

[4] In 1982,[5] Bentley moved to the Computer Science Research Center at Bell Laboratories, where he was Distinguished Member of the Technical Staff.

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

He wrote the Programming Pearls column for the Communications of the ACM magazine, and later collected the articles into two books of the same name in 1986 and 1988.