  We introduce the concept of an obstacle skeleton 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. A minimum
skeleton is a skeleton with the smallest possible number of line segments. We
provide an exact $O(n^2)$ algorithm for computing minimum skeletons for
rectilinear obstacles in the rectilinear plane that are rectilinearly-convex.
We show that the number of edges in a minimum skeleton is generally very small
compared to the number of edges in the boundary of the original obstacle, by
performing experiments on random rectilinearly-convex obstacles with up to 1000
vertices.
