Computing Shortest Paths among Curved Obstacles in the Plane

摘要

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(h(2)). 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+epsilon) h) time for any epsilon > 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: