Quasi-uniform designs from random candidates: optimal candidate complexity and farthest-point sampling

Abstract

We study randomized constructions of quasi-uniform designs on a compact metric-measure space satisfying two-sided polynomial ball-growth conditions. Given integers $N\le M$, we first draw $M$ independent candidate points and then retain the first $N$ points of a farthest-point traversal of the candidate set. We prove probabilistic non-asymptotic bounds on the mesh ratio and show that $M=\Theta (N\log N)$ is the sharp order of the candidate-pool size required for bounded mesh ratio: a sufficiently large multiple of $N\log (N/\delta )$ suffices with probability at least $1-\delta$, whereas, if $M=o(N\log N)$, the mesh ratio diverges in probability for every procedure that selects $N$ points from the same independent candidate pool. If $M/(N\log M)\to \infty$, the upper bound on the mesh ratio for the exact farthest-point sampling (FPS) tends to $2$. We also quantify the effect of approximate FPS and analyze direct and fast implementations in spaces of bounded doubling dimension. Finally, using a single infinite stream of candidate points and increasing candidate budgets, we construct an almost surely quasi-uniform nested sequence; under supercritical oversampling and exact FPS, or more generally when the approximation factors tend to $1$, its mesh-ratio limit superior equals $2$ for compact positive-volume subsets of Euclidean space.

arXiv comment39 pages, 5 figures