k-Pairs Non-Crossing Shortest Paths in a Simple Polygon
k-Pairs Non-Crossing Shortest Paths in a Simple Polygon
复制标题
简单多边形中的 k 对不相交最短路径
DOI：
10.1142/s0218195999000315
复制
发表时间：
1996
影响因子：
--
通讯作者：
Evanthia Papadopoulou
中科院分区：
文献类型：
--
作者：
Evanthia Papadopoulou
本文提出了一种O（n+k）时间算法，用于计算n个顶点的简单多边形边界上的k对源-目的点之间的k条不相交最短路径集。路径允许重叠，但不允许在平面上交叉。这个结果的副产品是一个O(n)时间算法来计算一个平衡的测地线三角形，这是容易实现的。该算法扩展到一个简单的单孔多边形，源目标对可以同时出现在多边形的内外边界上。在后一种情况下，目标是计算总成本最小的非交叉路径的集合。
This paper presents an O(n+k) time algorithm to compute the set of k non-crossing shortest paths between k source-destination pairs of points on the boundary of a simple polygon of n vertices. Paths are allowed to overlap but are not allowed to cross in the plane. A byproduct of this result is an O(n) time algorithm to compute a balanced geodesic triangulation which is easy to implement. The algorithm extends to a simple polygon with one hole where source destination pairs may appear on both the inner and outer boundary of the polygon. In the latter case, the goal is to compute a collection of non-crossing paths of minimum total cost.