Exact and Approximate Algorithms for Fréchet Problems

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


PhD Thesis Defence


Title: "Exact and Approximate Algorithms for Fréchet Problems"

By

Mr. Haoqiang HUANG


Abstract:

The advances of location-acquisition and mobile devices generate massive 
trajectory data and motivate trajectory ananlysis. Fréchet distance is 
a popular metric for measuring the similarity between trajectories. It 
appears in many algorithmic problems in trajectory analysis including curve 
simplification, clustering, nearest neighbor, and range searching queries. We 
present new algorithms for these problems under the Fréchet distance.

For curve simplification, we present a novel space of configurations and a 
useful geometric construct that lead us to the first bicriteria approximation 
scheme for curve simplification. We further extend these notions to a set of 
curves and design an algorithm to compute a simplified representative for 
multiple curves. By combining this technique with a framework in the 
literature, we obtain the first approximation algorithm for (k,ℓ)-median 
clustering under Fréchet distance.

We study the nearest neighbor problem. We design a scheme that allows us to 
transform a query curve into an encoding from a finite space. This encoding 
enables us to design the first approximate nearest neighbor data structure 
for polygonal curves in Rd under Fréchet distance that has a space complexity
dependent on the input size only.

We characterize Fréchet distance by a polynomial system and develop an 
algebraic geometric approach. This new algebraic perspective allows us to 
design exact algorithms for a wide range of problems including curve 
simplification, nearest neighbor and range searching, which are hitherto 
unknown.

Finally, we study the computational complexity and approximability of the 
Fréchet distance. We design the first subquadratic time algorithm for 
computing the Fréchet distance. We also show the first constant 
approximation algorithm for the Fréchet distance that runs in strongly 
subquadratic time.


Date:                   Monday, 2 December 2024

Time:                   2:00pm - 4:00pm

Venue:                  Room 5501
                        Lifts 25/26

Chairman:               Dr. Jun ZHANG (ECE)

Committee Members:      Prof. Siu-Wing CHENG (Supervisor)
                        Dr. Sunil ARYA
                        Prof. Ke YI
                        Prof. Ajay JONEJA (IEDA)
                        Dr. Hubert CHAN (HKU)