Computing Shortest Paths among Curved Obstacles in the Plane-猫眼课题宝

计算平面内弯曲障碍物之间的最短路径

DOI：

发表时间：

2015

期刊：

TALG

影响因子：

通讯作者：

中科院分区：

文献类型：

作者：

D. Chen;Haitao Wang

计算几何中的一个基本问题是计算平面上两点之间的避障欧几里德最短路径。这个问题在多边形障碍物上的情况已经得到了很好的研究。在本文中，我们考虑弯曲障碍物的问题版本，通常建模为样条线。样条线可以看作是用凸弯曲边代替多边形的每条边（多边形是特殊的样条线），并且假设每条弯曲边的组合复杂度为O(1)。给定平面中的两个点 s 和 t 以及一组 s，其中 h 个成对不相交样条线，总共有 n 个顶点，在获得 S 的 有界度分解 后，我们计算一条最短的 s 到 t 路径，以避免样条线O(n + h log h + k) 时间，其中 k 是对输入几何结构敏感的参数，上限为 O(h2)。 S 的有界度分解类似于多边形域的三角剖分，可以在 O(n log n) 时间或 O(n + h log 1 + εh) 时间内计算出任意值ε > 0。特别是，当所有样条都是凸的时，分解可以在 O(n + h log h) 时间内计算，并且 k 与样条之间自由空间中的公切线（称为“自由公切线”）的数量呈线性关系。我们的技术还改进了之前的几个结果： (1) 对于多边形情况（即，当所有样条都是多边形时），最短路径问题先前在 O(n log n) 时间内解决，或在 O(n + h2log n) 时间内解决。因此，我们的算法改进了 O(n + h2log n) 时间结果，并且对于足够小的 h 来说比 O(n log n) 时间解决方案更快，例如， h=o(&sqrt;n,logn. (2) 我们的技术为计算具有总共 n 个顶点的 h 成对不相交凸样条线之间的所有自由公切线的基本可见性问题产生了最佳输出敏感算法。我们的算法在 O(n + h log h + k) 时间和 O(n) 工作空间内运行，其中 k 是所有自由公切线的数量。请注意，k = O(h2)。即使对于所有样条线都是凸多边形的特殊情况，以前解决此可见性问题的最佳算法也需要 O(n + h2log n) 时间。 (3) 我们改进了之前的工作，计算复杂度为 O(1) 的凸伪盘中两点之间的最短路径。此外，我们技术的副产品是一个最佳的 O(n + h log h) 时间和 O(n) 空间算法，用于计算一组 h 成对不相交凸样条的 Voronoi 图，总共有 n 个顶点。

A fundamental problem in computational geometry is to compute an obstacle-avoiding Euclidean shortest path between two points in the plane. The case of this problem on polygonal obstacles is well studied. In this article, we consider the problem version on curved obstacles, which are commonly modeled as splinegons. A splinegon can be viewed as replacing each edge of a polygon by a convex curved edge (polygons are special splinegons), and the combinatorial complexity of each curved edge is assumed to be O(1). Given in the plane two points s and t and a set s of h pairwise disjoint splinegons with a total of n vertices, after a bounded degree decomposition of S is obtained, we compute a shortest s-to-t path avoiding the splinegons in O(n + h log h + k) time, where k is a parameter sensitive to the geometric structures of the input and is upper bounded by O(h2). The bounded degree decomposition of S, which is similar to the triangulation of the polygonal domains, can be computed in O(n log n) time or O(n + h log 1 + εh) time for any ε > 0. In particular, when all splinegons are convex, the decomposition can be computed in O(n + h log h) time and k is linear to the number of common tangents in the free space (called “free common tangents”) among the splinegons. Our techniques also improve several previous results: (1) For the polygon case (i.e., when all splinegons are polygons), the shortest path problem was previously solved in O(n log n) time, or in O(n + h2log n) time. Thus, our algorithm improves the O(n + h2log n) time result, and is faster than the O(n log n) time solution for sufficiently small h, for example, h=o(&sqrt;n,logn. (2) Our techniques produce an optimal output-sensitive algorithm for a basic visibility problem of computing all free common tangents among h pairwise disjoint convex splinegons with a total of n vertices. Our algorithm runs in O(n + h log h + k) time and O(n) working space, where k is the number of all free common tangents. Note that k = O(h2). Even for the special case where all splinegons are convex polygons, the previously best algorithm for this visibility problem takes O(n + h2log n) time. (3) We improve the previous work for computing the shortest path between two points among convex pseudodisks of O(1) complexity each. In addition, a by-product of our techniques is an optimal O(n + h log h) time and O(n) space algorithm for computing the Voronoi diagram of a set of h pairwise disjoint convex splinegons with a total of n vertices.

Computing Shortest Paths among Curved Obstacles in the Plane

计算平面内弯曲障碍物之间的最短路径

文献摘要

被引文献

相似文献