Worst case discrepancy for points in plane grows as log power three halves
Tight Bounds for Tusnády's Problem in the Plane
Computational Geometry
Summary
This paper looks at how unevenly we can split points on a plane when shading parts of it using rectangles aligned with the axes. The authors prove that in the worst case, the imbalance grows roughly like the logarithm of the number of points raised to the three-halves power. Earlier, only smaller and larger estimates were known, but this work shows the exact growth rate. Their method, surprisingly simple, examines one coordinate digit at a time and uses probability to handle random points.
What this means in practice
- •For computational geometers: Determine precise limits on discrepancy to guide design of geometry algorithms sensitive to point distribution irregularities.
- •For data structure designers: Rule out possibility of better discrepancy bounds when using axis-aligned rectangle queries on planar data sets.
A theory result. No direct application yet.
Authors
Zhewei Wei
Abstract
We show that the worst-case combinatorial discrepancy of $n$ points in the plane with respect to axis-parallel rectangles is $Θ(\log^{3/2}n)$. The known bounds were $Ω(\log n)$ and $O(\log^{3/2}n)$; we prove the matching lower bound. It holds for random point sets: for every $A>0$, there is a constant $c_A>0$ such that, with probability at least $1-e^{-An}$, every coloring of $n$ independent uniform points in the unit square has an anchored rectangle with imbalance at least $c_A(\log_2n)^{3/2}$. The proof is surprisingly simple and elementary. It reveals one coordinate digit by digit. With overwhelming probability over the points, the conditional gains of an oscillation potential add up to $Ω(\log^{3/2}n)$ over $Θ(\log n)$ digits. Bounded differences control the fluctuations well enough for a union bound over all colorings.