Computing Shortest Paths among Curved Obstacles in the Plane

Details Computing Shortest Paths among Curved Obstacles in the Plane Computing Shortest Paths among Curved Obstacles in the Plane

2011-03-21

arxiv.org/abs/1103.3911v1

Computer Science

Computational Geometry

41 pages, 20 figures

Scientific paper

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 paper, we consider the problem version on curved obstacles, 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). Each curved edge is assumed to be of O(1) complexity. Given two points s and t and $h$ splinegons of totally $n$ vertices with pairwise disjoint interior, we compute a shortest s-to-t path avoiding the splinegons, in $O(n+h\log^{1+\epsilon}h+k)$ time, where k is a parameter sensitive to the structures of the input splinegons and is bounded by $O(h^2)$. In particular, when all splinegons are convex, $k$ is proportional to the number of common tangents in the free space (called "free common tangents") among the splinegons. Previous work is known only for some special cases of this problem (e.g., when the obstacles are discs or certain convex objects). Our algorithm improves several previous results. (1) We improve the previously best solution for computing a shortest path between two points among convex pseudodisks of O(1) complexity each. (2) We even improve an algorithm for the polygon case (when all splinegons are polygons). The polygon case has been solved in $O(n \log n)$ time, or in $O(n+h^2\log n)$ time. Thus, we improve the $O(n+h^2\log n)$ time result. (3) We give an optimal algorithm for a basic visibility problem of computing all free common tangents among $h$ pairwise disjoint convex splinegons of totally $n$ vertices, in $O(n+k+h\log h)$ time and O(n) space, where k is the number of all free common tangents (and $k=O(h^2)$). Even for the special case when all splinegons are convex polygons, the previously best algorithm takes $O(n+h^2\log n)$ time.

Affiliated with

Also associated with

No associations

Rating

Computing Shortest Paths among Curved Obstacles in the Plane does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing Shortest Paths among Curved Obstacles in the Plane, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Shortest Paths among Curved Obstacles in the Plane will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-322350