乔恩·本特利 (计算机科学家)
乔恩·路易斯·本特利(英语:Jon Louis Bentley,1953年2月20日—)是一名美国计算机科学家,他提出了基于启发式的分区算法k-d树。
乔恩·本特利 Jon Bentley | |
---|---|
出生 | Jon Louis Bentley 1953年2月20日 ![]() |
母校 | 斯坦福大学(BS) 北卡罗来纳大学教堂山校区(MS、PhD) |
科学生涯 | |
机构 | 亚美亚 |
论文 | Divide and conquer algorithms for closest point problems in multidimensional space(1976) |
博士导师 | Donald Ford Stanat |
博士生 | 查尔斯·E·雷瑟尔森 凯瑟琳·麦姬奇 詹姆斯·B·萨克斯 |
生平
编辑本特利于1974年获得斯坦福大学数学科学学士学位,1976年获得北卡罗来纳大学教堂山校区数学科学硕士和博士学位;在校期间,他还曾在施乐帕洛阿尔托研究中心和史丹佛直线加速器中心实习[1]。获得博士学位后,他进入卡内基美隆大学任教,担任电脑科学和数学助理教授[1]。在卡内基美隆大学,他的学生包括布莱恩·里德、约翰·奥斯特豪特、杰夫·埃平格、约书亚·布洛克和詹姆斯·高斯林,他也是查尔斯·E·雷瑟尔森的导师之一[2]。后来,本特利来到贝尔实验室,与道格拉斯·麦克罗伊合著了一种优化的快速排序算法[3]。
他找到克利度量问题二维情形的最适解:给定一组 n 个矩形,求它们的结合面积。他和托马斯·奥特曼(Thomas Ottmann)发明本特利-奥特曼算法,这是一种在线段集合中寻找所有相交线对的高效算法。他为《ACM通讯》杂志撰写“程式设计珍珠”专栏,后来将这些文章汇集成两本同名书籍。
2004年,本特利荣获Dobb博士卓越程式设计奖。
参考书目
编辑- 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.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).
- ^ Jon Louis Bentley在数学谱系计划的资料。
- ^ Jon L. Bentley; M. Douglas McIlroy. Engineering a sort function. Software—Practice & Experience. November 1993, 23 (11).
- ^ 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
- Lucent Technologies press release [失效链接]
- 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).