三维空间中的最短路问题

被引：4

作者：

施海虎

机构：

[1] 海信集团技术中心!青岛北京大学计算机科学与技术系北京

来源：

软件学报 | 1999年 / 07期

关键词：

最短路; 凸多面体; 计算几何; 测地线; Voronoi图;

D O I：

暂无

中图分类号：

TP391.41 [];

学科分类号：

摘要：

在包含一组相互分离凸多面体的三维空间中为任意两点寻找最短路的问题是ＮＰ问题．当凸多面体的个数ｋ任意时，它为指数时间复杂度；而当ｋ＝１时，为Ｏ（ｎ２）（ｎ为凸多面体的顶点数）．文章主要研究了ｋ＝２情形下的最短路问题，提出一个在Ｏ（ｎ２）时间内解决该问题的算法．所得结果大大优于此情形下迄今为止最好的结果——Ｏ（ｎ３ｌｏｇｎ）．另外，将此结果应用到ｋ＞２的情形后，获得的结果为Ｏ（１２ｉ－１ｎ２ｉ）．

引用

页码：772 / 777

页数：6