Quasi-random points keep their distance (Q2372449)

For a given net, composed of \(N\) quasi-random points \(Q_{0}, Q_{1}, \dots , Q_{N-1}\) in the \(n\)-dimensional hypercube \(I^{n}\), the measure \(d_{N} = \min_{0 \leq i < j < N} \rho(Q_{i}, Q_{j}), \) where \(\rho\) is the Euclidean distance between the points \(Q_{i}\) and \(Q_{j},\) called minimum distance, is considered. In section 2 the behavior of \(d_{N}\) as \(N\) increases is investigated. Proposition 1 confirms that, for the initial segment of the Sobol sequence (\(LP_{\tau}\)-sequence) in \(I^{n}\), the minimum distance satisfies the estimation \(d_{N} \geq {1 \over 2} \sqrt{n}N^{-1}.\) It is shown that the order of the lower bound for \(d_{N}\) is exact at dimension \(n=1.\) Some analytical examples suggest that, for the initial segment of the Sobol sequence and for large \(N\), \(d_{N} \asymp N^{-{1 \over n}}.\) For some certain search algorithms, it is important to idendify pairs of quasi-random points \(Q_{i}\) and \(Q_{i+1}\) that are not too close. In section 3 such pairs are found. Proposition 2 gives that, for the initial segment of the Sobol sequence in \(I^{n}\), \( \rho(Q_{2k}, Q_{2k+1}) = {1 \over 2}\sqrt{n}.\) Proposition 3 gives a lower bound and an upper bound of the distance between \(Q_{4k+1}\) and \(Q_{4k+2}.\) It is shown that the lower bound in Proposition 3 is exact. In section 4 the results of sections 2 and 3 are extended to the Halton and Faure sequences. In section 5 a general upper bound for the minimum distance is given. Proposition 4 gives, that for any \(N > 2\) points in \(I^{n}\), the minimum distance satisfies the inequality \(d_{N} \leq A(n) \cdot N^{-{1 \over n}},\) with a constant \(A(n),\) depending on the dimension \(n.\)