A note on minimal dispersion of point sets in the unit cube
Jakub Sosnovec
cs.CG math.CO



 

Department of Computer Science,
University of Warwick
j.sosnovec@warwick.ac.uk
This work was supported by the Leverhulme Trust 2014 Philip Leverhulme Prize of Daniel Král'.


We study the dispersion of a point set, a notion closely related to the discrepancy. Given a real r∈(0,1) and an integer d≥ 2, let N(r,d) denote the minimum number of points inside the d-dimensional unit cube [0,1]^d such that they intersect every axis-aligned box inside [0,1]^d of volume greater than r. We prove an upper bound on N(r,d), matching a lower bound of Aistleitner et al. up to a multiplicative constant depending only on r. This fully determines the rate of growth of N(r,d) if r∈(0,1) is fixed.


A note on minimal dispersion of point sets in the unit cube
    Jakub Sosnovec
    December 30, 2023
===========================================================






§ INTRODUCTION

The geometric discrepancy theory is the study of distributions of finite point sets and their irregularities <cit.>. 

In this note, we study a notion closely related to discrepancy, the dispersion of a point set.

The problem of finding the area of the largest empty axis-parallel rectangle amidst a set of points in the unit square is a classical problem in computational geometry. The algorithmic version has been introduced by Naamad et al. <cit.> and several other algorithms have been proposed over the years, such as <cit.>. The problem naturally generalizes to multi-dimensional variant, where the task is to determine the volume of the largest empty box amidst a set of points in the d-dimensional unit cube. 

An active line of research concerns general bounds on the volume of largest empty box for any set of points, in terms of the dimension and the number of points. An upper bound thus amounts to exhibiting an example of a point set such that the volume of any empty box is small, while the lower bound asks for the minimal value such that every set of points of given cardinality allows an empty box of that volume. The first results in this direction were given by Rote and Tichy <cit.>. Dumitrescu and Jiang <cit.> first showed a non-trivial lower bound, which was later improved by Aistleitner et al. <cit.>. An upper bound by Larcher is also given in <cit.>. Rudolf <cit.> has found an upper bound with much better dependence on the dimension. The problem has recently received attention due to similar questions appearing in approximation theory <cit.>, discrepancy theory <cit.> and approximation of L_p-norms and Marcinkiewicz-type discretization <cit.>.

The following reformulation is of interest in the applications in approximation theory: If we fix r∈(0,1) to be the “allowed volume”, how many points in ℝ^d are needed to force that any empty box has volume at most r, in terms of d? In other words, we ask for the minimum number of points needed to intersect every box of volume greater than r. 
In this note, we establish the optimal asymptotic growth of this quantity for r fixed.



 §.§ Notation

For a positive integer k, let [k] denote the set {1,2,…,k}. If x∈ℝ^d is a vector, (x)_i denotes the i-th coordinate of x. Let 1 denote the vector (1,…,1)∈ℝ^d (where d will always be clear from context). 

For d≥ 2, we use [0,1]^d to denote the d-dimensional unit cube. A box B=I_1×⋯× I_d⊆ [0,1]^d is open (closed) if all of I_1,…,I_d are open (closed) intervals. We define ℬ_d as the family of all open boxes inside [0,1]^d. 

For a set T of n points in [0,1]^d, the volume of the largest open axis-parallel box avoiding all points from T is called the dispersion of T and is defined as

    (T)=sup_B∈ℬ_d,  B∩ T=∅(B),

where (I_1×⋯× I_d)=|I_1|⋯|I_d|. Note that the supremum in (<ref>) is attained, since there are only finitely many inclusion-maximal boxes B∈ℬ_d avoiding T. 

We further define the minimal dispersion for any point set as

    ^*(n,d)=inf_T⊂[0,1]^d, |T|=n(T).

Again, observe that the infimum in (<ref>) is actually attained, since any sequence of n-element point sets inside [0,1]^d has a convergent subsequence.

The quantity we mainly consider in this paper is the inverse function of the minimal dispersion,

    N(r,d)=min{n∈ℕ:^*(n,d)≤ r},

where r∈(0,1). Determining N(r,d) thus corresponds to the question of how many points are needed to intersect every box of volume greater than r.

We remark that the functions ^*(n,d) and N(r,d) are of course tightly connected and any bounds on them translate between each other. 



 §.§ Previous work

The trivial lower bound on ^*(n,d) is 1/(n+1), since we can split the cube into n+1 parts and use the pigeonhole principle. This was improved in <cit.> to

    ^*(n,d)≥log_2d/4(n+log_2d).


The inequality (<ref>) can be reformulated to give a lower bound on N(r,d) for r∈(0,1/4),

    N(r,d)≥1-4r/4rlog_2 d.

In order to show (<ref>), the same authors prove an auxiliary lemma, which is equivalent to that

    N(1/4,d)≥log_2(d+1).

Thus for r∈(0,1/4] fixed, we have N(r,d)=Ω(log d).

On the other hand, Larcher (with proof also given in <cit.>) has found the following upper bound of the right order in n,

    ^*(n,d)≤2^7d+1/n.

For large enough n, this is the best bound. However, the dependence on d is exponential, which was recently greatly improved by Rudolf <cit.> as follows, 

    ^*(n,d)≤4d/nlog(9n/d).


The best upper bound on the inverse of the minimal dispersion for r∈(0,1/4] fixed, which is the setting of this paper, is the reformulation of (<ref>),

    N(r,d)≤ 8d qlog(33q),

where q=1/r. Thus for r∈(0,1/4] fixed, we have N(r,d)=O(d).





 §.§ Our results

We are interested in determining the asymptotic growth of N(r,d) for r∈(0,1) fixed and d tending to infinity. As it turns out, the rate of growth is different for r∈(0,1/4] and r∈(1/4,1). 
    
First, we show that for r∈(1/4,1), the number N(r,d) is in fact bounded by a constant depending only on r. This is in sharp contrast with (<ref>) which implies that N(r,d)→∞ for d→∞ if r<1/4.

For every r∈(1/4,1), there exists a constant c_r∈ℕ such that for every d≥ 2,

    N(r,d)≤ c_r.

In particular, c_r can be set as 
    ⌊1/(r-1/4)⌋ + 1.


Then we show an upper bound for r∈(0,1/4] which matches the lower bound (<ref>) up to a multiplicative constant depending only on r.

For every r∈(0,1/4], there exists a constant c'_r∈ℝ such that for every d≥ 2,

    N(r,d)≤ c'_rlog d.

In particular, c'_r can be set as q^q^2+2(4log q + 1), where q=⌈ 1/r⌉.

This fully determines the asymptotic growth of N(r,d) in terms of d.

Let r∈(0,1) be fixed and d tend to infinity. If r∈(0,1/4], then N(r,d)=Θ(log d), otherwise N(r,d)=O(1).










§ PROOFS



We proceed with the proof of Theorem <ref>.

First, consider the case r∈[1/2,1). We set c_r=1 and claim that the single central point 1/2·1∈[0,1]^d does not allow an empty box of volume greater than 1/2. Let B=I_1×⋯× I_d∈ℬ_d be such that 1/2·1∉ X, then there exists a coordinate i∈[d] such that 1/2∉I_i. Hence |I_i|≤ 1/2 and the claim follows.

Let us now assume r∈(1/4,1/2). We set

    δ=r-1/4>0 and k_0=⌊1/δ⌋
 
and define the set 

    X={kδ·1:k∈[k_0]}∪{1/2·1}.

Note that X is thus a set of points all lying on the diagonal of the unit cube and |X|≤ k_0 + 1=c_r. 

Let B=I_1×⋯× I_d∈ℬ_d be a box such that B∩ X=∅. Again, let i∈[d] be such that 1/2∉I_i. If |I_i|≤ 1/4, then (B)≤ 1/4≤ r, so we can assume |I_i|>1/4≥δ. Also, we have either I_i⊂[0,1/2] or I_i⊂[1/2,1], without loss of generality assume the former (the argument for the other case is symmetric). 

Let α∈(0,1/2] be the right endpoint of the interval I_i and choose k∈[k_0] maximal so that kδ<α (such k exists, as |I_i|>δ). Observe that kδ∈ I_i, but we assumed kδ·1∉B, therefore there exists an index j∈[d], distinct from i, such that kδ∉ I_j. It follows that |I_j|≤ 1-kδ. Finally, by the definition of k, we have α-kδ≤δ and hence |I_j|≤ 1-α+δ. We conclude

    (B)≤|I_i|· |I_j|≤α(1-α+δ)≤α(1-α)+δ≤ 1/4+δ= r.





To prove Theorem <ref>, we use the probabilistic method to construct a set of points that does not allow any empty box of volume greater than r. 

Let q be defined as ⌈ 1/r⌉. In the following, we will assume that 1/r is an integer – this is without loss of generality, as otherwise we can use the construction for 1/⌈ 1/r⌉. 

Let X be the set of 

    n=q^q^2+2(4log q + 1)log d

points inside [0,1]^d chosen independently and uniformly at random from the grid {1/q,2/q,…,(q-1)/q}^d. Let ℬ_d^r⊂ℬ_d be the set of all boxes of volume greater than r. We now have to show that the probability that X intersects every box from ℬ_d^r is positive.

For a box B=I_1×⋯× I_d∈ℬ_d^r, let the number of coordinates i∈[d] such that |I_i|≤ 1-r be equal to m_B. We have

    r<(B)≤ (1-r)^m_B,

obtaining that m_B≤ M for 

    M=⌊log r/log (1-r)⌋.


The critical part of our proof is the following observation. There exists a finite family 𝒬_d^r of closed boxes inside [0,1]^d such that every open box B∈ℬ_d^r contains an element of 𝒬_d^r as a subset. Moreover, the cardinality of 𝒬_d^r will be at most (dq)^M.

To see this, observe that for every box B=I_1×⋯× I_d∈ℬ_d^r, we can find (possibly non-unique) indices 1≤ j_1<j_2<⋯<j_M≤ d and values k_j_1,…,k_j_M∈[q-1] such that 


  * |I_i|> (q-1)/q for all i∈ [d]∖{j_1,…,j_M} and

  * k_j_ℓ/q∈ I_j_ℓ for all ℓ∈[M]. 

We can obtain <ref> from the fact that (q-1)/q=1-r and the definition of m_B, and <ref> from |I_i|>r=1/q for all i∈[d]. 

For every such combination of j_1,…,j_M∈[d] and k_j_1,…,k_j_M∈[q-1], we will include in 𝒬_d^r the closed box Q=J_1×⋯× J_d⊂ [0,1]^d with 

    J_i=
    
    [1/q,(q-1)/q]    if i∈ [d]∖{j_1,…,j_M},
    {k_i/q}    otherwise.


We claim that 𝒬_d^r satisfies the desired condition. For every B∈ℬ_d^r and corresponding indices j_1,…,j_M∈ [d] and values k_j_1,…,k_j_M∈[q-1], the closed box Q as defined above is contained within B by <ref> and <ref>. Moreover, we can bound the cardinality of 𝒬_d^r as follows, 

    |𝒬_d^r|=dM(q-1)^M≤(dq)^M.
 

By the property of 𝒬_d^r, if X intersects every box in 𝒬_d^r, then it also intersects every box in ℬ_d^r. We thus only need to show that with positive probability, X intersects every box in 𝒬_d^r. 

Let us fix indices j_1,…,j_M∈[d] and values k_j_1,…,k_j_M∈[q-1] and the corresponding closed box Q=J_1×⋯× J_d∈𝒬_d^r. Clearly, J_i=[1/q,(q-1)/q] implies that any choice of (x)_i will intersect J_i. Hence, the only coordinates restricting intersections with X are j_1,…,j_M. Moreover, for each of (x)_j_1,…,(x)_j_M, there is exactly one choice of k∈[q-1] such that k=k_j_ℓ.

We obtain that for a point x∈{1/q,2/q,…,(q-1)/q}^d chosen uniformly at random,

    ℙ[x∈ Q]= (1/q-1)^M>r^M.

Therefore, we get

    ℙ[X∩ Q = ∅]<(1-r^M)^n≤exp(-nr^M),

and, by the union bound,

    ℙ[X∩ Q' = ∅ for some Q'∈𝒬_d^r]     <(dq)^Mexp(-nr^M).


If the right hand side of (<ref>) is bounded by one, then there exists a choice of X such that it intersects every box in 𝒬_d^r. We bound the logarithm of the right hand side. Using the fact that M ≤ q^2 and the definition of n, we obtain 

    Mlog d+Mlog q - nr^M    ≤ q^2log d + q^2log q - nq^-q^2
        = q^2log d + q^2log q - q^2(4log q + 1)log d
        = (1 - 4log d)q^2log q ≤ 0,

where the last inequality follows from d≥ 2. This concludes the proof of Theorem <ref>.




§ ACKNOWLEDGEMENTS


The author would like to thank Dan Král' for introducing him to the problem and Jan Vybíral for some initial thoughts and a major simplification of the proof of Theorem <ref>. The author would also like to acknowledge the discussions held in Oberwolfach Workshop Perspectives in High-Dimensional Probability and Convexity, as shared to him by Jan Vybíral.


  abbrv
  

