Exact and Approximate Solutions for Fréchet Problems
- Haoqiang Huang, HKUST
- Time: 2023-12-27 16:00
- Host: Dr. Shaofeng Jiang
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
In this talk, we will present several new algorithmic results regarding polygonal curves under Fréchet distance, including curve simplification, clustering, nearest neighbor, and some others.
In the first part, we will focus on the first bicriteria approximation scheme for curve simplification under Fréchet distance. We will present a novel discretization of the searching space and a useful geometric construct that lead us to the approximation scheme. With further development, the discretization strategy provides us with an encoding scheme for an arbitrary curve with respect to a set of fixed curves. This new encoding scheme allows us to design the first approximate nearest neighbor data structure for polygonal curves in d-dimensional space under the Fréchet distance with bounded space complexity for d larger than 1.
In the second part, we will switch our attention to exact solutions. We will 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 solutions for a wide range of problems including curve simplification and nearest neighbor, which are unknown until this work.
Biography
Haoqiang Huang is current a fourth-year Ph.D. student at HKUST under the supervision of Prof. Siu-Wing Cheng. He received his B. Eng in the School of Computer Science and Technology at USTC. His research interests lie in computational geometry and especially the algorithmic problems motivated by data mining on trajectories and time series.