272 citations · 611 across the 76 of their papers we have counts for
8 papers · 1 filter
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…
Edge Estimation with Independent Set Oracles
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy +2
We study the task of estimating the number of edges in a graph with access to only an independent set oracle. Independent set queries draw motivation from group testing and have ap…
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…