28 citations · 244 across the 83 of their papers we have counts for
5 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…
Prophet Secretary: Surpassing the Barrier
Yossi Azar, Ashish Chiplunkar, Haim Kaplan
In the Prophet Secretary problem, samples from a known set of probability distributions arrive one by one in a uniformly random order, and an algorithm must irrevocably pick one of…
Pairing heaps: the forward variant
Dani Dorfman, Haim Kaplan, László Kozma +1
The pairing heap is a classical heap data structure introduced in 1986 by Fredman, Sedgewick, Sleator, and Tarjan. It is remarkable both for its simplicity and for its excellent pe…
Clustering Small Samples with Quality Guarantees: Adaptivity with One2all pps
Edith Cohen, Shiri Chechik, Haim Kaplan
Clustering of data points is a fundamental tool in data analysis. We consider points in a relaxed metric space, where the triangle inequality holds within a constant factor. Th…
Voronoi diagrams on planar graphs, and computing the diameter in deterministic time
Paweł Gawrychowski, Haim Kaplan, Shay Mozes +2
We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let be a planar graph with vertices and sites that lie on a…