4 papers
A Dimension-Reducing Fréchet Simplification Oracle
Boris Aronov, Tsuri Farhana, Matthew J. Katz +1
Let be a polygonal curve with vertices in the plane. We construct a data structure of size suited for simplification queries of the following kind. Given a qu…
Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs
Tsuri Farhana, Omrit Filtser, Shalev Goldshtein
We study unlabeled MRMP for unit-disk robots in a polygonal environment. Although the problem is hard in general, polynomial-time solutions exist under appropriate separation assum…
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 can be computed in strictly subquadratic time. We thus consider the setting where one of the curv…
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 -spanner of a planar point-set is a -Hausdorff-spanner…