跳转到内容

乔恩·本特利 (计算机科学家)

维基百科,自由的百科全书
乔恩·本特利
Jon Bentley
出生Jon Louis Bentley
(1953-02-20) 1953年2月20日71岁)
 美国加利福尼亚州长滩[1]
母校斯坦福大学BS
北卡罗来纳大学教堂山校区MSPhD
科学生涯
机构亚美亚
论文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

乔恩·路易斯·本特利(英语:Jon Louis Bentley,1953年2月20日)是一名美国计算机科学家,他提出了基于启发式的分区算法k-d树

生平

本特利于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. ^ 1.0 1.1 1.2 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. 

外部链接