Back to search

Carleton University

Shortest path queries on polyhedral sufaces and in polygonal domains

Abstract

dc:description.abstract

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=1wi|πi|, where |πi| = π∩fidenotes the Euclidean length of the subpath of π within face fiwhose 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(n2log n) time to support distance queries for any pair of query points in PD in O(h log n) time.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (Ph.D.)
Level thesis:degree_level
Doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
Carleton University
Year dc:date.issued
2010

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Guo, Hua

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • Copyright © 2010 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Carleton University
Base URL
carleton.scholaris.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Guo, Hua. Shortest path queries on polyhedral sufaces and in polygonal domains. Doctoral thesis, Carleton University, 2010. https://hdl.handle.net/20.500.14718/27140