Shortest Path Queries on Triangular Irregular Networks and Point Clouds

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Shortest Path Queries on Triangular Irregular Networks and Point 
Clouds"

By

Mr. Yinzhao YAN


Abstract:

Performing shortest path queries on a 3D surface is a topic of widespread 
interest in 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 shortest path 
query algorithms on a TIN are inefficient, and there is no existing shortest 
path query algorithm on a point cloud. In this thesis, we study how to 
effectively calculate the shortest path passing on a TIN and a point cloud 
in three aspects. (1) We propose an efficient on-the-fly shortest path 
algorithm answering the shortest path passing different regions on a 
weighted TIN, where different regions are assigned different weights. (2) We 
propose an efficient updatable shortest path oracle answering the shortest 
path query for a set of Points-Of-Interests (POIs) on an updated TIN. (3) We 
propose an efficient shortest path oracle answering the shortest path query 
for a set of POIs on a point cloud, and an efficient proximity query 
algorithm using our oracle. Our experimental results show that they 
outperform the best-known algorithms or oracles concerning time and memory.


Date:                   Tuesday, 29 July 2025

Time:                   8:30am - 11:00am

Venue:                  Room 3494
                        Lifts 25/26

Chairman:               Prof. Andrew Wing On POON (ECE)

Committee Members:      Prof. Raymond WONG (Supervisor)
                        Dr. Binhang YUAN
                        Prof. Xiaofang ZHOU
                        Prof. Xueqing ZHANG (CIVL)
                        Prof. Cyrus SHAHABI (USC)