An Efficient Algorithm for Euclidean Shortest Paths Among Polygonal Obstacles in the Plane
An Efficient Algorithm for Euclidean Shortest Paths Among Polygonal Obstacles in the Plane
复制标题
DOI：
10.1007/pl00009323
复制
发表时间：
1997-12
影响因子：
0.8
通讯作者：
Sanjiv Kapoor;S. N. Maheshwari;Joseph S B Mitchell
中科院分区：
文献类型：
--
作者：
Sanjiv Kapoor;S. N. Maheshwari;Joseph S B Mitchell
本文给出了一个计算n个顶点、有h个洞的多边形中的（欧几里德）最短路的算法。该算法使用O（n）空间，需要时间。
We give an algorithm to compute a (Euclidean) shortest path in a polygon withhholes and a total ofnvertices. The algorithm usesO(n)space and requirestime.