Computing Shortest Paths among Curved Obstacles in the Plane

摘要

In this paper, we study the problem of finding Euclidean shortest paths among curved obstacles in the plane. We model curved obstacles as splinegons. A splinegon can be viewed as replacing each edge of a polygon by a convex curved edge, and each curved edge is assumed to be of O(1) complexity. Given in the plane two points s and t and a set of h pairwise disjoint splinegons with a total of n vertices, we present an algorithm that can compute a shortest path from s to t avoiding the splinegons in O(n + h log~(1+e) h + k) time for any e ＞ 0, where k is a parameter sensitive to the input splinegons and k = O(h~2). If all splinegons are convex, a common tangent of two splinegons is 'free' if it does not intersect the interior of any splingegon; our techniques yield an output sensitive algorithm for computing all free common tangents of the h splinegons in O(n + h log h + k) time and O(n) working space, where k is the number of all free common tangents.