Siu-Wing Cheng

activity

20232025

collaborators

7 papers

cs.CG2025

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time

Siu-Wing Cheng, Haoqiang Huang, Shuo Zhang

Let $τ$ and $σ$ be two polygonal curves in $R^{d}$ for any fixed $d$ . Suppose that $τ$ and $σ$ have $n$ and $m$ vertices, respectively, and $m \leq n$ . While conditional lower…

cs.CG2025

Simplification of Trajectory Streams

Siu-Wing Cheng, Haoqiang Huang, Le Jiang

While there are software systems that simplify trajectory streams on the fly, few curve simplification algorithms with quality guarantees fit the streaming requirements. We present…

cs.CG2024

Fréchet Distance in Subquadratic Time

Siu-Wing Cheng, Haoqiang Huang

Let $m$ and $n$ be the numbers of vertices of two polygonal curves in $R^{d}$ for any fixed $d$ such that $m \leq n$ . Since it was known in 1995 how to compute the Fréchet d…

cs.CG2023

Geometric Matching and Bottleneck Problems

Sergio Cabello, Siu-Wing Cheng, Otfried Cheong +1

Let $P$ be a set of at most $n$ points and let $R$ be a set of at most $n$ geometric ranges, such as for example disks or rectangles, where each $p \in P$ has an associated supply…

cs.CG2023

Solving Fréchet Distance Problems by Algebraic Geometric Methods

Siu-Wing Cheng, Haoqiang Huang

We study several polygonal curve problems under the Fréchet distance via algebraic geometric methods. Let $X_{m}^{d}$ and $X_{k}^{d}$ be the spaces of all polygonal curve…

cs.CG2023

Solving Proximity Problems for Polygonal Shapes via Polynomials

Frederik Brüning, Siu-Wing Cheng, Anne Driemel +1

We study range spaces, where the ground set consists of either polygonal curves in $R^{d}$ or polygonal regions in the plane that may contain holes and the ranges are balls…

cs.CG2023

Approximate Nearest Neighbor for Polygonal Curves under Fréchet Distance

Siu-Wing Cheng, Haoqiang Huang

We propose $κ$ -approximate nearest neighbor (ANN) data structures for $n$ polygonal curves under the Fréchet distance in $R^{d}$ , where $κ\in \{1+\varepsilon,3+\varepsilon\}…