Carleton University
Shortest path queries on polyhedral sufaces and in polygonal domains
Abstract
dc:description.abstractIn 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 × 3Rights
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