5 papers
Minimum-Complexity Graph Simplification under Fréchet-Like Distances
Omrit Filtser, Majid Mirzanezhad, Carola Wenk
Simplifying graphs is a very applicable problem in numerous domains, especially in computational geometry. Given a geometric graph and a threshold, the minimum-complexity graph sim…
Static and Streaming Data Structures for Fréchet Distance Queries
Arnold Filtser, Omrit Filtser
Given a curve with points in in a streaming fashion, and parameters and , we construct a distance oracle that uses $O(\frac{1}{\varepsilon})^{…
A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon
Stav Ashur, Omrit Filtser, Matthew J. Katz
The problem of vertex guarding a simple polygon was first studied by Subir K. Ghosh (1987), who presented a polynomial-time -approximation algorithm for placing as few g…
Efficient Nearest-Neighbor Query and Clustering of Planar Curves
Boris Aronov, Omrit Filtser, Michael Horton +2
We study two fundamental problems dealing with curves in the plane, namely, the nearest-neighbor problem and the center problem. Let be a set of polygonal curves,…
The Discrete Fréchet Gap
Omrit Filtser, Matthew J. Katz
We introduce the discrete Fréchet gap and its variants as an alternative measure of similarity between polygonal curves. We believe that for some applications the new measure (and…