Geometric discrepancy

Geometric discrepancy theory ^[1] is a sub-field of discrepancy theory, that deals with balancing geometric sets, such as intervals or rectangles. The general research question in this field is: given a set of points in a geometric space, and a set of objects in the same space, can we color each point in one of two different colors (e.g. black and white), such that each object contains roughly the same number of points of each color?

Formally, the discrepancy of an object is defined as the difference between the number of white points and the number of black points in that object; the objective is to color the points such that the maximum discrepancy of an object is as small as possible.

Intervals

In the simplest geometric discrepancy setting, the set of objects is the set of all sub-intervals of the real interval [0,1]. In this setting, it is possible to attain discrepancy 1: simply color the points alternately black - white - black - white - etc. Then, the discrepancy of every interval is either 0 or 1.

The problem becomes more challenging when the points are not available in advance, but arrive one by one, and each point should be colored immediately when it arrives. This setting is called the "Online Interval Discrepancy". Jiang, Kulkarni and Singla prove that: ^{[2] : Sec.3.2}

• No online algorithm can guarantee a constant discrepancy.
• Randomly coloring each point when it arrives gives ${\displaystyle {\tilde {O}}({\sqrt {n}})}$ expected discrepancy.
• If the point arrival is adversarial, the discrepancy of any online algorithm is ${\displaystyle \Omega ({\sqrt {n}})}$.
• If the point arrival is stochastic, there is an efficient algorithm that guarantees ${\displaystyle O(n^{c/\log {\log {n}}})}$ discrepancy, for some universal constant c, with high probability (i.e. with probability 1-1/poly(n), where the exponent of the polynomial depends on c).

Their proof uses a reduction to the problem of Online Tree Balancing, which is a problem of discrepancy in which the set of objects is the set of sub-trees of a complete m-ary tree with height h. For this problem, they prove that, if ${\displaystyle h\leq {\log \log n}/C}$ for a sufficiently large constant C, and m ≥ 100, then there is an online algorithm that attains discrepancy ${\displaystyle O(\log ^{2}n)}$. ^{[2] : Sec.2}

Rectangles and boxes

Tusnady asked what is the discrepancy when the set of objects is the set of axes-parallel rectangles contained in the unit square.

• Beck ^[3] proved that the discrepancy is at least Ω(log n) and at most O(log⁴n).
• Nikolov ^[4] proved that the discrepancy is at most O(log^1.5n).

When the set of objects is the set of all rectangles (possibly rotated), then:

• Beck ^[3] proved that the discrepancy is at least Ω(n^1/4-ε) and at most O(n^1/2+ε) for any ε>0.

Matousek ^[5] studied the d-dimensional extension of Tusnady's problem. Improving previous results by Roth, Schmidt, Beck, Bohus, and Srinivasan, he proved an upper bound of ${\displaystyle O_{d}((\log n)^{d+1/2}{\sqrt {\log \log n}})}$ with a simple proof.

Stripes

When the set of objects is the set of stripes—rectangles of the form [a,b]x[0,1] and [0,1]x[a,b], the setting is equivalent to the problem of "two permutations": given two permutations on a set of n elements, we should color each element either black or white, such that the discrepancy in each interval of each permutation is minimized (the two permutations are the order of the x coordinates and the order of the y coordinates of the points).

• Spencer proved that it is possible to attain a discrepancy of at most 2. ^[2]

Jiang, Kulkarni and Singla ^[2] study the online setting with stochastic point arrival, and prove that:

• A random coloring yields an expected discrepancy of ${\displaystyle {\tilde {O}}({\sqrt {n}})}$.
• There is an efficient algorithm that guarantees ${\displaystyle O(n^{c/\log {\log {n}}})}$ discrepancy, for some universal constant c, with high probability. They show an application of this result to online fair division.

Convex polytopes

Matousek ^[5] and Nikolov ^[4] studied a more general setting, where the set of objects is induced by dilations and translations of a fixed convex polytope. He proved upper and lower bounds on the discrepancy. The results are analogous to the results for rectangles and boxes.

Half-spaces

When the set of objects is the set of half-spaces in the Euclidean d-dimensional space:

• Alexander ^[5] proved a lower bound of ${\displaystyle \Omega (n^{1/2-d/2})}$ for any dense point set, that is, the ratio of maximum and minimum interior distances is in O(n^1/d).
• Matousek ^[6] proved an upper bound of ${\displaystyle C_{d}n^{1/2-d/2}}$. In fact, this upper bound holds not only for half-spaces but also for any set system for which the primal shatter function is in O(m^d).

References

1. Matoušek, Jiří (1999). Geometric Discrepancy: An Illustrated Guide. Springer. ISBN   3-540-65528-X.
2. Jiang, Haotian; Kulkarni, Janardhan; Singla, Sahil (2019-10-02). "Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization". arXiv: 1910.01073 [cs.DS].
3. Beck, József (1981-12-01). "Balanced two-colorings of finite sets in the square I". Combinatorica. 1 (4): 327–335. doi:10.1007/BF02579453. ISSN   1439-6912.
4. Nikolov, Aleksandar (January 2017). "Tighter Bounds for the Discrepancy of Boxes and Polytopes". Mathematika. 63 (3): 1091–1113. arXiv: 1701.05532 . doi:10.1112/S0025579317000250. ISSN   0025-5793.
5. Alexander, R. (1990-06-01). "Geometric methods in the study of irregularities of distribution". Combinatorica. 10 (2): 115–136. doi:10.1007/BF02123006. ISSN   1439-6912.
6. Matoušek, J. (1995-06-01). "Tight upper bounds for the discrepancy of half-spaces". Discrete & Computational Geometry. 13 (3): 593–601. doi:10.1007/BF02574066. ISSN   1432-0444.