喬恩·本特利 (計算機科學家)

喬恩·路易斯·本特利（英語：Jon Louis Bentley，1953年2月20日—）是一名美國計算機科學家，他提出了基於啟發式的分區演算法k-d樹。

喬恩·本特利 Jon Bentley
出生	Jon Louis Bentley (1953-02-20) 1953年2月20日（71歲）  美國加利福尼亞州長灘^[1]
母校	史丹佛大學（BS） 北卡羅來納大學教堂山校區（MS、PhD）
科学生涯
机构	亞美亞
论文	Divide and conquer algorithms for closest point problems in multidimensional space（1976）
博士導師	Donald Ford Stanat
博士生	查爾斯·E·雷瑟爾森（英语：Charles E. Leiserson） 凱瑟琳·麥姬奇（英语：Catherine McGeoch） 詹姆斯·B·薩克斯（英语：James B. Saxe）

生平

本特利於1974年獲得史丹佛大學數學科學學士學位，1976年獲得北卡羅來納大學教堂山校區數學科學碩士和博士學位；在校期間，他還曾在施樂帕洛阿爾托研究中心和史丹佛直線加速器中心實習^[1]。獲得博士學位後，他進入卡內基美隆大學任教，擔任電腦科學和數學助理教授^[1]。在卡內基美隆大學，他的學生包括布萊恩·里德（英语：Brian Reid (computer scientist)）、約翰·奧斯特豪特（英语：John Ousterhout）、傑夫·埃平格（英语：Jeff Eppinger）、約書亞·布洛克和詹姆斯·高斯林，他也是查爾斯·E·雷瑟爾森（英语：Charles E. Leiserson）的導師之一^[2]。後來，本特利來到貝爾實驗室，與道格拉斯·麥克羅伊合著了一種優化的快速排序演算法^[3]。

他找到克利度量問題（英语：Klee's measure problem）二維情形的最適解：給定一組 n 個矩形，求它們的結合面積。他和托馬斯·奧特曼（Thomas Ottmann）發明本特利-奧特曼演算法（英语：Bentley–Ottmann algorithm），這是一種在線段集合中尋找所有相交線對的高效演算法。他為《ACM通訊》雜誌撰寫「程式設計珍珠」專欄，後來將這些文章匯集成兩本同名書籍。

2004年，本特利榮獲Dobb博士（英语：Dr. Dobb's Journal）卓越程式設計獎。

參考書目

• Programming Pearls (2nd edition), ISBN 0-201-65788-0.
• More Programming Pearls: Confessions of a Coder, ISBN 0-201-11889-0.
• Writing Efficient Programs, ISBN 0-13-970244-X.
• Divide and Conquer Algorithms for Closest Point Problems in Multidimensional Space, Ph.D. thesis.^[4]

參考資料

1. Biography from Bentley, J. L.; Ottmann, T. A., Algorithms for reporting and counting geometric intersections (PDF), IEEE Transactions on Computers, 1979, C–28 (9): 643–647, S2CID 1618521, doi:10.1109/TC.1979.1675432, （原始内容于September 22, 2017） .
2. Jon Louis Bentley在數學譜系計畫的資料。
3. Jon L. Bentley; M. Douglas McIlroy. Engineering a sort function. Software—Practice & Experience. November 1993, 23 (11). 
4. Bentley, Jon L. Divide and conquer algorithms for closest point problems in multidimensional space.. 1976. 

外部連結

• www.cs.bell-labs.com/cm/cs/pearls/code.html on GitHub
• ^{[失效連結]}
• bug in Jon Bentley's binary search - google research
  • The C Programming Language, 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).