272 citations · 371 across the 32 of their papers we have counts for
7 papers · 2 filters
Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
Esther Ezra, Sariel Har-Peled, Haim Kaplan +1
We re-examine parameters for the two main space decomposition techniques---bottom-vertex triangulation, and vertical decomposition, including their…
Journey to the Center of the Point Set
Sariel Har-Peled, Mitchell Jones
We revisit an algorithm of Clarkson et…
Grid peeling and the affine curve-shortening flow
David Eppstein, Sariel Har-Peled, Gabriel Nivasch
In this paper we study an experimentally-observed connection between two seemingly unrelated processes, one from computational geometry and the other from differential geometry. Th…
A Simple Algorithm for Computing a Cycle Separator
Sariel Har-Peled, Amir Nayyeri
We present a linear time algorithm for computing a cycle separator in a planar graph that is (arguably) simpler than previously known algorithms. Our algorithm builds on, and is so…
On Separating Points by Lines
Sariel Har-Peled, Mitchell Jones
Given a set of points in the plane, its separability is the minimum number of lines needed to separate all its pairs of points from each other. We show that the minimum num…
LSH on the Hypercube Revisited
Sariel Har-Peled, Sepideh Mahabadi
LSH (locality sensitive hashing) had emerged as a powerful technique in nearest-neighbor search in high dimensions [IM98, HIM12]. Given a point set in a metric space, and given…