Efficient algorithms for shortest path and visibility problems
John E. Hershberger · 1987
Finding shortest paths and determining visibilities are problems encountered every day. Formal versions of these problems are important in computational geometry. Both kinds of problems specify a space and a set of opaque, impenetrable obstacles in the space. Visibility problems ask what an observer would see if placed in the space; shortest path problems seek the minimum length route for an object moving among the obstacles. This thesis provides algorithms for several visibility and shortest path problems, illuminating the relationship between the two classes. The first part of the thesis considers problems in which the space is the plane and the obstacles are non-intersecting line segments. It presents a worst-case-optimal algorithm to find the visibility graph of the set of segments; that is, it computes what would be seen by observers standing at all the segment endpoints. It then uses this information to find shortest paths for a non-rotating convex body moving among the segments. The second part of the thesis provides several optimal algorithms for shortest path and visibility problems inside simple polygons that have already been triangulated. In this setting, the polygon walls are the only obstacles. The most basic problem considered is that of finding all shortest paths from a particular vertex to other vertices. The solution to this problem can be applied to solve several visibility problems, including that of finding the visibility graph of a simple polygon in time proportional to its size. The thesis concludes by presenting geometric structures and corresponding data structures to solve several query problems efficiently, including the following: the shooting problem, which asks where a bullet fired inside a polygon would hit its boundary, and the two-point shortest path problem, which asks for the length of the shortest path between two arbitrary query points. Throughout the thesis, solutions to shortest path problems help solve visibility problems, and vice versa. The use of a single technique to solve problems of both classes demonstrates the close ties between the two.