Speaker: Haoqiang Huang, HKUST

Time: 16:00 p.m., December 27, 2023, GMT+8

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.

Source: Center on Frontiers of Computing Studies, PKU