21 papers
How to Catch Grid Points
Sariel Har-Peled, Elfarouk Harb, Qizheng He
Given a positive integer , we study the problem of finding a convex polygon of minimum perimeter that encloses exactly points of . We show that an optimal poly…
The Prophet and the Voronoi Diagram
Sariel Har-Peled
Consider a stream of random points (say, from the unit square) arriving one by one, where a player has to make an irreversible immediate decision for each arriving point whethe…
Separator for -Packed Segments and Curves
Sariel Har-Peled
We provide a simple algorithm for computing a balanced separator for a set of segments that is -packed, showing that the separator cuts only segments. While the result wa…
Approximately: Independence Implies Vertex Cover
Sariel Har-Peled
We observe that a $(1-\eps)$-approximation algorithm to Independent Set, that works for any induced subgraph of the input graph, can be used, via a…
Graph-Based Nearest-Neighbor Search without the Spread
Jeff Giliberti, Sariel Har-Peled, Jonas Sauer +1
Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set of points in , such that one can answer ap…
On Small Pair Decompositions for Point Sets
Kevin Buchin, Jacobus Conradi, Sariel Har-Peled +5
$\newcommand{\Re}{\mathbb{R}}$We study the minWSPD problem of computing the minimum-size well-separated pairs decomposition of a set of points, and show constant approximation algo…