| 三维空间中的最短路问题 |
| |
| 引用本文： | 施海虎.三维空间中的最短路问题[J].软件学报,1999,10(7):772-777. |
| |
| 作者姓名： | 施海虎 |
| |
| 作者单位： | 海信集团技术中心,青岛,266071；北京大学计算机科学与技术系,北京,100871 |
| |
| 基金项目： | 本文研究得到国家自然科学基金、国家863高科技项目基金和中国科学院院长特别基金资助. |
| |
| 摘 要： | 在包含一组相互分离凸多面体的三维空间中为任意两点寻找最短路的问题是NP问题.当凸多面体的个数k任意时,它为指数时间复杂度;而当k=1时,为O(n2)（n为凸多面体的顶点数）.文章主要研究了k=2情形下的最短路问题,提出一个在O(n2)时间内解决该问题的算法.所得结果大大优于此情形下迄今为止最好的结果——O(n3
|
| 关 键 词： | 最短路 凸多面体 计算几何 测地线 Voronoi图. |
| 收稿时间： | 1997/11/11 0:00:00 |
| 修稿时间： | 1998/7/20 0:00:00 |
The Problem of Shortest Path in 3D Space |
| |
| SHI Hai-hu.The Problem of Shortest Path in 3D Space[J].Journal of Software,1999,10(7):772-777. |
| |
| Authors: | SHI Hai-hu |
| |
| Affiliation: | SHI Hai hu(Hisense Technique Research Center Qingdao 266071) (Department of Computer Science and Technology Beijing University Beijing 100871) |
| |
| Abstract: | |
| |
| Keywords: | Shortest path convex polyhedron computing geometry geodesics Voronoi graph |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
