乔恩·本特利 (计算机科学家)
| 乔恩·本特利 Jon Bentley | |
|---|---|
| 出生 | Jon Louis Bentley 1953年2月20日  美国加利福尼亚州长滩[1] |
| 母校 | 斯坦福大学（BS） 北卡罗来纳大学教堂山校区（MS、PhD） |
| 科学生涯 | |
| 机构 | 亚美亚 |
| 论文 | Divide and conquer algorithms for closest point problems in multidimensional space（1976） |
| 博士导师 | Donald Ford Stanat |
| 博士生 | 查尔斯·E·雷瑟尔森 凯瑟琳·麦姬奇 詹姆斯·B·萨克斯 |
乔恩·路易斯·本特利（英语：Jon Louis Bentley，1953年2月20日—）是一名美国计算机科学家，他提出了基于启发式的分区算法k-d树。
生平
[编辑]本特利于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).
