OpenAlex ·
Tight Bounds for Tusnády's Problem in the Plane
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.08130
- Original
- Read it at the publisher
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
PhysLDM: Latent Diffusion for High-Fidelity Deformable Simulation
Co${}^{2}$Skill: Whole-Body Control via Skill Composition for Long-Horizon Human-Environment Interaction
UltraDiff: Differentiable Ray Tracing in Ultrasound for Shape Optimization
emg2face: Expressive Facial Animation with High-Density Surface EMG
View Matters: Keyframe-Guided Text-Driven 3D Gaussian Editing
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.