Shortest Path Queries Between Geometric Objects on Surfaces

摘要

We consider geometric shortest path queries between arbitrary pairs of objects on a connected polyhedral surface P of genus g. The query objects are points, vertices, edges, segments, faces, chains, regions and sets of these. The surface P consists of n positively weighted triangular faces. The cost of a path on P is the weighted sum of Euclidean lengths of the sub-paths within each face of P. We present generic algorithms which provide approximate solutions.