Efficient Algorithms for Shortest Path and Visibility Problems,
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1987
- Accession Number
- ADA325211
Entities
People
- John E. Hershberger
Organizations
- Stanford University