Accession Number : ADA325211

Title :   Efficient Algorithms for Shortest Path and Visibility Problems,

Descriptive Note : Doctoral thesis,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Hershberger, John E.

PDF Url : ADA325211

Report Date : JUN 1987

Pagination or Media Count : 191

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.

Descriptors :   *ALGORITHMS, *POSITION FINDING, DATA BASES, OPTIMIZATION, GRAPHS, THESES, VISIBILITY, COMPUTER VISION, ONLINE SYSTEMS, COLLISION AVOIDANCE, POINT THEOREM, POLYGONS, STRUCTURED PROGRAMMING, TRIANGULATION, CONVEX BODIES.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE