In this thesis, we present algorithmic solutions to shortest path queries on polyhedral surfaces and in polygonal domains. The research problems addressed in this thesis and shortest path problems in general are fundamental problems in geographic information systems (GIS) and computational geometry.

We present novel algorithms that answer approximate shortest path queries between any pair of points lying on a polyhedral surface P consisting of n positively weighted triangular faces. The cost of a path, denoted by ||π||, in P is defined as ||π| |= Σni=1 wi|πi|, where |πi| = π∩fi denotes the Euclidean length of the subpath of π within face fi whose weight is wi.

Our all-pairs query algorithm takes as input an approximation parameter ε ∈ (0,1) and a query time parameter q, in a certain range, and builds a data structure APQ(P, ε; q) for answering ε-approximate distance queries in O(q) time. When the surface P is homeomorphic to a planar domain, we present a space-efficient algorithm which exploits the planarity of P. As a building block of APQ(P, ε; q), we develop a single-source query data structure SSQ(P, ε; a) which answers ε-approximate distance queries from a fixed point a to any query point in P in logarithmic time. These proposed algorithms are important extension, both theoretically and practically, to the extensively studied Euclidean distance case. They are based on a novel graph sparator algorithm which extends and/or generalizes many previously known results.

Moreover, we consider queries between arbitrary pairs of objects lying on P, where query objects are points, segments, faces, chains, regions and sets of these. We present generic algorithms which provide approximate solutions.

Lastly, we consider shortest path queries in a polygonal domain PD having n vertices and h holes. A skeleton graph is a subgraph of a Voronoi diagram of PD. Our new algorithm utilizes a reduced skeleton graph of PD to compute a tessellation of PD. It builds a data structure of size O(n2) in O(n2 log n) time to support distance queries for any pair of query points in PD in O(h log n) time.