Computing Skeletons for Rectilinearly Convex Obstacles in the Rectilinear Plane

摘要

We introduce the concept of an obstacleskeleton, which is a set of line segments inside a polygonal obstacle omega that can be used in place of omega when performing intersection tests for obstacle-avoiding network problems in the plane. A skeleton can have significantly fewer line segments compared to the number of line segments in the boundary of the original obstacle, and therefore performing intersection tests on a skeleton (rather than the original obstacle) can significantly reduce the CPU time required by algorithms for computing solutions to obstacle-avoidance problems. Aminimum skeletonis a skeleton with the smallest possible number of line segments. We provide an exact O(n(2)) lgorithm for computing minimum skeletons for rectilinear obstacles in the rectilinear plane that are rectilinearly convex.