16 citations · 39 across the 12 of their papers we have counts for
4 papers · 1 filter
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α…
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 $\…