On Shallow Packings and Tusnády's Problem
share
Tusnády's problem asks to bound the discrepancy of points and axis-parallel boxes in ℝ^d. Algorithmic bounds on Tusnády's problem use a canonical decomposition of Matoušek for the system of points and axis-parallel boxes, together with other techniques like partial coloring and / or random-walk based methods. We use the notion of shallow cell complexity and the shallow packing lemma, together with the chaining technique, to obtain an improved decomposition of the set system. Coupled with an algorithmic technique of Bansal and Garg for discrepancy minimization, which we also slightly extend, this yields improved algorithmic bounds on Tusnády's problem. For d≥ 5, our bound matches the lower bound of Ω(log^d-1n) given by Matoušek, Nikolov and Talwar [IMRN, 2020] – settling Tusnády's problem, upto constant factors. For d=2,3,4, we obtain improved algorithmic bounds of O(log^7/4n), O(log^5/2n) and O(log^13/4n) respectively, which match or improve upon the non-constructive bounds of Nikolov for d≥ 3. Further, we also give improved bounds for the discrepancy of set systems of points and polytopes in ℝ^d generated via translations of a fixed set of hyperplanes. As an application, we also get a bound for the geometric discrepancy of anchored boxes in ℝ^d with respect to an arbitrary measure, matching the upper bound for the Lebesgue measure, which improves on a result of Aistleitner, Bilyk, and Nikolov [MC and QMC methods, Springer, Proc. Math. Stat., 2018] for d≥ 4.
READ FULL TEXT