Matthew J. Katz

activity

20232026

collaborators

3 papers

cs.CG2026

A Dimension-Reducing Fréchet Simplification Oracle

Boris Aronov, Tsuri Farhana, Matthew J. Katz +1

Let $P$ be a polygonal curve with $n$ vertices in the plane. We construct a data structure of size $O (n lo g n)$ suited for simplification queries of the following kind. Given a qu…

cs.CG2024

Discrete Fréchet Distance Oracles

Boris Aronov, Tsuri Farhana, Matthew J. Katz +1

It is unlikely that the discrete Fréchet distance between two curves of length $n$ can be computed in strictly subquadratic time. We thus consider the setting where one of the curv…

cs.CG2023

Spanners under the Hausdorff and Fréchet Distances

Tsuri Farhana, Matthew J. Katz

We initiate the study of spanners under the Hausdorff and Fréchet distances. We show that any $t$ -spanner of a planar point-set $S$ is a $\frac{t ^{2} - 1}{2}$ -Hausdorff-spanner…