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≤ 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=Θ(Nlog N) is the sharp order of the candidate-pool size required for bounded mesh ratio: a sufficiently large multiple of Nlog(N/δ) suffices with probability at least 1−δ, whereas, if M=o(Nlog N), the mesh ratio diverges in probability for every procedure that selects N points from the same independent candidate pool. If M/(Nlog M)→∞, 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.
Related
- Uniform Sampling of Linear Codes with Prescribed Hull Dimension
- High-Arity Rademacher Complexity and Uniform Laws of Large Numbers
- Non-Uniform Random Scans in Gibbs Sampling and CAVI
- A sharp bound for sampling widths in the uniform norm: kernel D-optimal designs and oversampling
- Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start
BibTeX
@misc{goda2026quasiuniform,
title = {{Quasi-uniform designs from random candidates: optimal candidate complexity and farthest-point sampling}},
author = {Takashi Goda and Hengjun Xu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05986},
eprint = {2609.05986},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05986},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Quasi-uniform designs from random candidates: optimal candidate complexity and farthest-point sampling
AU - Takashi Goda
AU - Hengjun Xu
PY - 2026
DA - 2026/09/05
PB - arXiv
DO - 10.48550/arxiv.2609.05986
UR - https://arxiv.org/abs/2609.05986
AB - We study randomized constructions of quasi-uniform designs on a compact metric-measure space satisfying two-sided polynomial ball-growth conditions. Given integers N≤ 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=Θ(Nlog N) is the sharp order of the candidate-pool size required for bounded mesh ratio: a sufficiently large multiple of Nlog(N/δ) suffices with probability at least 1−δ, whereas, if M=o(Nlog N), the mesh ratio diverges in probability for every procedure that selects N points from the same independent candidate pool. If M/(Nlog M)→∞, 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.
ER -