Exact and Approximate Algorithms for Fréchet Problems

PhD Thesis Proposal Defence


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

by

Mr. Haoqiang HUANG


Abstract:

Fréchet distance is a popular distance metric for measuring the similarity 
between curves. It appears in many algorithmic problems motivated by the 
analysis of curves and trajectories like curve simplification, clustering, 
nearest neighbor/range searching queries. We present new algorithms for these 
problems under the Fréchet distance.

First, we consider curve simplification and clustering. 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,l)-median clustering under Fréchet distance.

Then, we turn to the nearest neighbor problem. We design an encoding scheme for 
an arbitrary curve with respect to a set of fixed curves. This encoding scheme 
allows us to transform a query curve into an encoding from a finite space, 
which enables us to design the first approximate nearest neighbor data 
structure for polygonal curves in d-dimensional space under the Fréchet 
distance that has a space complexity dependent on the input size only.

Finally, we switch our attention to exact algorithms. We characterize Fréchet 
distance by a polynomial system and study multiple Fréchet problems via 
algebraic methods. This new algebraic perspective allows us to get exact 
algorithms for a wide range of problems including curve simplification, nearest 
neighbor and range searching, which are unknown until our work.


Date:                   Monday, 11 March 2024

Time:                   2:00pm - 4:00pm

Venue:                  Room 5501
                        Lifts 25/26

Committee Members:      Prof. Siu-Wing Cheng (Supervisor)
                        Prof. Dimitris Papadias (Chairperson)
                        Prof. Ke Yi
                        Dr. Sunil Arya