Papers for

data structure designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Worst case discrepancy for points in plane grows as log power three halves

Tight Bounds for Tusnády's Problem in the Plane

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.

Tue 6 OctComputational Geometry

The gist

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.

Open → 2610.08130v1