1 citations · 1 across the 13 of their papers we have counts for
16 papers · 1 filter
Segment Watchman Routes
Anna Brötzner, Omrit Filtser, Bengt J. Nilsson +2
Motivated by applications for robust guarding, we consider a variant of the multiple-watchmen problem that ensures that every point within a polygon is seen from more than one…
On Fréchet Traveling Salesmen Problems
Omrit Filtser, Tzalik Maimon, Michal Moiseev
The Fréchet distance is a well-studied distance measure between two curves. In this work, we demonstrate that the merit of Fréchet distance extends beyond evaluating similarity, an…
Peeling Rotten Potatoes for a Faster Approximation of Convex Cover
Omrit Filtser, Tzalik Maimon, Ofir Yomtovyan
The minimum convex cover problem seeks to cover a polygon with the fewest convex polygons that lie within . This problem is -complete, and the best previou…
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…
Robustly Guarding Polygons
Rathish Das, Omrit Filtser, Matthew J. Katz +1
We propose precise notions of what it means to guard a domain "robustly", under a variety of models. While approximation algorithms for minimizing the number of (precise) point gua…
Guarding Polyominoes Under -Hop Visibility
Omrit Filtser, Erik Krohn, Bengt J. Nilsson +2
We study the Art Gallery Problem under -hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest p…
On Flipping the Fréchet distance
Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell +1
The classical and extensively-studied Fréchet distance between two curves is defined as an inf max, where the infimum is over all traversals of the curves, and the maximum is over…
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})^{…
Plurality in Spatial Voting Games with constant
Arnold Filtser, Omrit Filtser
Consider a set of voters, represented by a multiset in a metric space . The voters have to reach a decision -- a point in . A choice is called a -pluralit…
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,…
Approximate Nearest Neighbor for Curves: Simple, Efficient, and Deterministic
Arnold Filtser, Omrit Filtser, Matthew J. Katz
In the -approximate near-neighbor problem for curves (ANNC) under some distance measure , the goal is to construct a data structure for a given set $\mathcal{…
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…
On the Chain Pair Simplification Problem
Chenglin Fan, Omrit Filtser, Matthew J. Katz +2
The problem of efficiently computing and visualizing the structural resemblance between a pair of protein backbones in 3D has led Bereg et al. to pose the Chain Pair Simplification…
The Discrete and Semi-continuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection Techniques
Rinat Ben Avraham, Omrit Filtser, Haim Kaplan +2
The \emph{Fréchet distance} is a well studied similarity measures between curves. The \emph{discrete Fréchet distance} is an analogous similarity measure, defined for a sequence $A…