Finding Shortest Gentle Paths

MPhil Thesis Defence


Title: "Finding Shortest Gentle Paths"

By

Mr. Lian Liu


Abstract

Shortest path query is a fundamental operator in spatial databases, which has a 
wide range of applications to both academia and industry. Although shortest 
path problems in graphs and in planes are well-studied, there are not much 
studies about finding shortest paths on terrain surfaces. Besides, few related 
studies consider the slope of paths.

In this thesis, we propose an algorithm for finding slope-constrained shortest 
paths or simply finding shortest gentle paths on terrain surfaces. The 
algorithm guarantees that the slope of the path does not exceed a maximum slope 
value defined by users, and the length of the path is the shortest among all 
such paths. Since traditional surface shortest paths can be viewed as shortest 
gentle paths with a maximum slope value equal to π/2, our problem is more 
general than the traditional surface shortest path problem. Besides, in some 
applications where time is a critical factor, a much faster (1+ε)-approximate 
algorithm is also proposed.

The algorithms are evaluated with both real terrain data sets including Eagle 
Peak (Wyoming State, U.S.A) and Bearhead (Washington State, U.S.A) and 
synthetic data sets.


Date:			Friday, 6 August 2010

Time:			10:30am - 12:30pm

Venue:			Room 3501
 			Lifts 25/26

Committee Members:	Dr. Raymond Wong (Supervisor)
 			Prof. Dik-Lun Lee (Chairperson)
 			Prof. Dit-Yan Yeung


**** ALL are Welcome ****