28 citations · 244 across the 83 of their papers we have counts for
6 papers · 1 filter
Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information
Edith Cohen, Haim Kaplan
Random sampling is an essential tool in the processing and transmission of data. It is used to summarize data too large to store or manipulate and meet resource constraints on band…
Unit Distances in Three Dimensions
Haim Kaplan, Jiri Matousek, Zuzana Safernova +1
We show that the number of unit distances determined by n points in R^3 is O(n^{3/2}), slightly improving the bound of Clarkson et al. established in 1990. The new proof uses the r…
Finding the Maximal Empty Rectangle Containing a Query Point
Haim Kaplan, Micha Sharir
Let be a set of points in an axis-parallel rectangle in the plane. We present an -time algorithm to preprocess into a data structure of size $O(nα…
Kinetic Stable Delaunay Graphs
Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas +4
We consider the problem of maintaining the Euclidean Delaunay triangulation $\DT$ of a set of moving points in the plane, along algebraic trajectories of constant descripti…
Non-Price Equilibria in Markets of Discrete Goods
Avinatan Hassidim, Haim Kaplan, Yishay Mansour +1
We study markets of indivisible items in which price-based (Walrasian) equilibria often do not exist due to the discrete non-convex setting. Instead we consider Nash equilibria of…
Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique
Haim Kaplan, Jiří Matoušek, Micha Sharir
Recently Guth and Katz \cite{GK2} invented, as a step in their nearly complete solution of Erdős's distinct distances problem, a new method for partitioning finite point sets in $\…