Shortest Path Queries on Terrain Surfaces and Point Clouds

PhD Thesis Proposal Defence


Title: "Shortest Path Queries on Terrain Surfaces and Point Clouds"

by

Mr. Yinzhao YAN


Abstract:

Performing shortest path queries on a 3D surface has gained significant 
attention from both industry and academia. Among different representations 
of a 3D surface, the most popular representations are Triangular-Irregular 
Network, i.e., TIN, and point cloud. However, all existing algorithms for 
answering shortest path queries on a TIN are inefficient, and there is no 
existing study focusing on answering shortest path queries directly on a 
point cloud. In this thesis, we study how to effectively calculate the 
shortest path passing on a TIN and a point cloud.

Firstly, we study shortest path queries on a weighted TIN using an 
on-the-fly algorithm. Specifically, we propose an efficient 
(1+epsilon)-approximate on-the-fly shortest path algorithm, that answers the 
shortest path between two points passing different regions on a weighted 
TIN, where different regions are assigned different weights. Our 
experimental results show that it is up to 1,630 times and 40 times better 
than the best-known algorithm on a weighted TIN in terms of the query time 
and memory usage, with an error at most 1%, respectively.

Secondly, we study proximity queries, i.e., shortest path queries, k-Nearest 
Neighbor (kNN) queries and range queries, on a point cloud using an oracle. 
Specifically, we propose an efficient (1+epsilon)-approximate shortest path 
oracle, that answers the shortest path query for a set of 
Points-Of-Interests (POIs) on a point cloud. It can be easily adapted to the 
case if POIs are not given as input. Then, we propose efficient algorithms 
for answering the (1+epsilon)-approximate kNN and range query with the 
assistance of our oracle. Our experimental results show that when POIs are 
given (resp. not given) as input, our oracle is up to 390 times, 30 times 
and 6 times (resp. 500 times, 140 times and 50 times) better than the 
best-known adapted oracle (which is the oracle on a TIN) in terms of the 
oracle construction time, oracle size and shortest path query time, 
respectively. Our algorithms for the other two proximity queries are both up 
to 100 times faster than the best-known adapted algorithm (which is the 
algorithm on a TIN), with an error at most 8%, respectively.


Date:                   Wednesday, 26 February 2025

Time:                   1:00pm - 3:00pm

Venue:                  Room 4472
                        Lifts 25/26

Committee Members:      Prof. Raymond Wong (Supervisor)
                        Prof. Dimitris Papadias (Chairperson)
                        Prof. Pedro Sander
                        Prof. Xiaofang Zhou