PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Takashi Goda, Hengjun Xu

arXiv:2609.05986v1math.NAcs.NA

TL;DR

Continuous farthest-point search can be difficult to implement on general domains, and prior finite-candidate results did not specify how to generate or size the candidate set. This paper uses iid candidate pools and farthest-point sampling, proving a sharp N log N candidate threshold. It also establishes near-2 mesh-ratio bounds and a nested-sequence limit result under stated conditions.

  • Problem

    Continuous largest-empty-ball searches may be unavailable or expensive on general domains, while prior finite-candidate control did not specify candidate generation or pool size.

    Source: §1 · p. 2

  • Method

    The method draws an iid candidate pool from a full-support measure and selects points by exact or approximate farthest-point sampling, with increasing budgets for a nested construction.

    Source: §1 · pp. 2, 4

  • Results

    M = Θ(N log N) is the sharp iid candidate-pool order for bounded mesh ratio, and the exact-FPS upper bound tends to 2 when M/(N log M)→∞.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    A sufficiently large multiple of N log(N/δ) candidates gives bounded mesh ratio with probability at least 1−δ, while subcritical pools fail for every candidate-thinning procedure.

    Source: §1 · pp. 3–4

    The critical regime M = C N log N remains less precisely understood, including how the best mesh-ratio bound depends on C and whether sharp domain-specific thresholds exist.

    Source: §7 · p. 37

Abstract

from arXiv · show

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.

1 Introduction

The paper replaces difficult continuous-domain farthest-point searches with randomized finite candidate pools, then studies how many candidates are needed for quasi-uniform designs. It establishes a sharp iid candidate-pool threshold, analyzes approximate and faster sampling, and extends the construction to nested sequences.

1 Introduction

  • The continuous greedy-packing method has mesh ratio at most 2, but finding each largest empty ball may be unavailable or expensive on general compact domains.Finite-candidate FPS offers a practical alternative, while earlier deterministic control by candidate covering radius did not specify how to generate or size the candidate set.Source: §1 · p. 2
  • The method needs only a sampling procedure for µ, a distance oracle, and M and N; it avoids repeated continuous largest-empty-ball searches and explicit boundary parametrization.The candidate cloud discretizes the domain, and FPS converts its covering property into covering and separation guarantees for the selected subset.Source: §1 · pp. 3–4
  • At the target resolution, about N disjoint regions each have probability mass on the order of N^-1, giving empty-region elimination the coupon-collector scale N log N.The coverage requirement concerns the ambient space, not connectivity among sampled vertices.Source: §1 · p. 3
  • When M/(N log M)→∞, the upper bound on exact FPS mesh ratio tends to 2.This is an upper-bound statement for separately constructed point sets, not a claim that each set's mesh ratio converges to 2.Source: §1 · p. 3
  • M = Θ(N log N) is the sharp iid candidate-pool order for bounded mesh ratio: enough candidates suffice for exact FPS, while subcritical pools fail for every thinning procedure.A sufficiently large multiple of N log(N/δ) gives bounded mesh ratio with probability at least 1−δ; if M=o(N log N), the mesh ratio diverges in probability.Source: §1 · pp. 3–4
  • Approximate FPS enlarges the exact-FPS mesh-ratio bound essentially by 1/α, separating search error from random candidate discretization error.The approximation factor controls how closely each selected point approaches the farthest available candidate.Source: §1 · p. 4
  • In bounded-doubling spaces, combining candidate-complexity bounds with greedy-permutation algorithms yields end-to-end cost O(N log^2 N) for fixed approximation accuracy and intrinsic dimension.Direct exact FPS instead uses O(MN) distance evaluations and O(M) storage.Source: §1 · p. 4
  • For compact positive-volume Euclidean subsets, the nested construction has mesh-ratio limit superior 2 when candidate budgets are supercritical and approximation factors tend to 1.The value is exact by the lower bound for every nested sequence on these domains.Source: §1 · p. 4

2 Preliminaries

The preliminaries set the compact metric-measure setting and define the geometric scales used to assess point sets. They then introduce random candidate clouds and exact or approximate farthest-point sampling.

2 Preliminaries

  • The framework assumes a compact metric space with positive diameter and a non-atomic Borel probability measure whose support is the whole space.Full support is needed for iid candidates to cover the domain, and non-atomicity makes independently sampled candidates distinct almost surely.Source: §2 · p. 5

2.1 Metric-measure spaces and geometric regularity

  • An s-regular space has ball masses bounded above and below by constant multiples of r^s, with s called its intrinsic dimension.This small-scale condition includes regular Euclidean domains and compact manifolds, and implies finite doubling dimension.Source: §2.1 · pp. 5–6

2.2 Covering and separation radii, and mesh ratio

  • In an s-regular space, the natural covering and separation scales for quasi-uniform N-point sets are N^-1/s.Quasi-uniformity is equivalent to having covering radius at most this order and separation radius at least this order, uniformly in N.Source: §2.2 · p. 7

2.3 Random candidate sets

  • The candidate cloud's covering radius measures its discretization error relative to the whole domain, and its probabilistic behavior is studied separately from algorithmic randomness.The candidates are distinct almost surely under the non-atomicity assumption.Source: §2.3 · p. 8

2.4 Exact and approximate farthest-point sampling

  • Exact FPS repeatedly selects a remaining candidate farthest from the points already chosen; approximate FPS requires each selected point's distance to the current set to be at least α_n times the residual candidate covering radius.Setting every α_n to 1 recovers exact FPS; finite-candidate sampling relaxes the continuous rule through candidate discretization and inexact search.Source: §2.4 · p. 8

3 Exact farthest-point sampling from random candidates

The section analyzes exact FPS on an iid candidate cloud by separating deterministic discretization error from random covering error. It establishes probabilistic mesh-ratio bounds and identifies the sharp candidate-pool order for bounded mesh ratios.

3 Exact farthest-point sampling from random candidates

  • The analysis combines deterministic candidate-set estimates with probabilistic control of candidate covering error to obtain non-asymptotic bounds for exact FPS.The lower-bound argument further shows that the iid pool-size requirement applies even when FPS is replaced by arbitrary subset selection.Source: §3 · p. 9

3.1 Deterministic candidate-set estimates

  • For every candidate set, the mesh-ratio bound is 2 plus a discretization term 2ε_M/R_{n−1}, and the estimate uses only metric structure.The discretization term measures candidate covering error relative to the insertion scale.Source: §3.1 · p. 10

3.2 Non-asymptotic probabilistic bounds

  • For candidate pools growing faster than the critical order, the mesh-ratio upper bound for separately constructed point sets tends to 2; this does not mean each set’s mesh ratio converges to 2.An individual finite point set may have mesh ratio smaller than 2.Source: §3.2 · p. 13

3.3 Optimal candidate-pool complexity

  • M = Θ(N log N) is the sharp iid candidate-pool order: a sufficiently large multiple suffices for exact FPS, while o(N log N) candidates fail for every selection rule.The lower bound follows because every selected subset inherits large empty regions in the candidate cloud.Source: §3.3 · pp. 15–16

4 Approximate and fast farthest-point sampling

This section analyzes the geometric effects of approximate farthest-point sampling and develops faster exact and approximate implementations. It interprets these methods through metric nets and maximal independent sets, and examines a grid-based multiscale implementation, its computational-cost and mesh-ratio bounds, a Euclidean spatial-hashing approach, and related greedy-permutation algorithms.

4.5 Euclidean implementation and end-to-end complexity

  • For fixed-dimensional Euclidean spaces, the section outlines a spatial-hashing implementation of multiscale FPS and derives end-to-end complexity bounds.The section also describes combining an exact greedy-permutation algorithm for doubling metrics with a probabilistic bound on the random candidate cloud’s spread.Source: §4 · p. 16

4.1 Mesh-ratio bounds for approximate sampling

  • For small errors, the excess mesh-ratio bound over 2 is first order in the approximation error and εM/h*_{N−1}(X).The deterministic approximate-FPS bounds extend those for exact FPS; a probabilistic bound is also obtained for s-regular spaces.Source: §4.1 · pp. 16–17
  • With M/(N log M)→∞ and minimum approximation factor tending to 1, the maximum prefix mesh ratio is asymptotically bounded by 2.The result assumes an s-regular space and applies to approximation factors that may vary with N.Source: §4.1 · p. 17

4.2 Direct and fast exact implementations

  • At M=⌈C N log N⌉, exact FPS achieves a prescribed mesh-ratio bound B>2 with cost O(N log^2 N) with probability tending to 1.The direct implementation costs O(MN) distance evaluations and comparisons with O(M) auxiliary storage; the faster random-cloud implementation computes a complete greedy permutation in O(M log(M/δ)) time and O(M) space with probability at least 1−δ.Source: §4.2 · pp. 18–20

4.3 A multiscale approximate FPS algorithm

  • With parameter β>1, multiscale approximate FPS terminates after selecting exactly N points and returns a β−1-approximate farthest-point traversal.It scans candidates at geometrically decreasing thresholds and stops as soon as N points are selected, without requiring a prescribed distance scale.Source: §4.3 · p. 20

4.4 Metric-net interpretation and maximal independent sets

  • Exact FPS yields cardinality-controlled nested metric nets, while a single-scale maximal independent set is scale-controlled and has cardinality of order N when M is of order N log N.Completed multiscale scans are maximal independent sets at their respective scales; stopping between scales gives the hierarchical net mechanism underlying approximate FPS.Source: §4.4 · pp. 23–24

4.5 Euclidean implementation and end-to-end complexity

  • O(C_d M K) distance evaluations and expected arithmetic time suffice for the grid implementation, with O(M + N) storage.The bound assumes Euclidean distances and standard constant-expected-time hashing.Source: §4.5 · p. 24
  • With the theorem’s condition satisfied, the mesh ratio is at most B on an event of probability at least 1 − δ, and grid cost is O(C_d M K).The theorem assumes an s-regular Euclidean metric-measure space and parameters β > 1 and B > 2β.Source: §4.5 · pp. 24–25
  • O(N log^2 N) is the multiscale method’s cost when M ≍ N log N, for fixed approximation parameter and dimension.The number of levels is logarithmic in N under these fixed-parameter conditions.Source: §4.5 · p. 25
  • For 0 < η ≤ 1, the corollary sets β = 1 + η/3 and B = 2(1 + η), with K = O(η^-1 log N).The proof establishes the mesh-ratio bound using 2β/(1 − τ_N,M,δ) ≤ 2(1 + η).Source: §4.5 · p. 25
  • Har-Peled and Mendel,, and provide alternative greedy-permutation algorithms, whose approximation guarantees can be translated into the factors α_n.The cited methods include hierarchical nets, a deterministic approximate permutation, and randomized algorithms for graph metrics and high-dimensional Euclidean point sets.Source: §4.5 · p. 25

5 Construction of a quasi-uniform nested sequence

The nested construction uses one infinite iid stream and increasing candidate pools to produce an almost surely quasi-uniform sequence. The section establishes the candidate-budget conditions for this guarantee and for an optimal limiting mesh ratio.

5 Construction of a quasi-uniform nested sequence

  • A single infinite iid candidate stream and increasing pools produce one sequence whose initial segments are almost surely quasi-uniform.Source: §5 · p. 26

5.1 A single-stream randomized construction

  • At each step, the construction retains earlier points and selects an approximately farthest candidate; its continuous-domain greedy quality depends on the FPS approximation and candidate covering error.Source: §5.1 · p. 26

5.2 Almost-sure control of the candidate covering errors

  • Summable failure probabilities ensure that candidate pools eventually meet the prescribed covering-error bound almost surely, providing coverage control for the nested analysis.Source: §5.2 · p. 28

5.3 Sharp candidate budgets

  • For M_n = (C + o(1))n log n, the theorem gives almost-sure quasi-uniformity when θ_C < 1 and lim inf α_n > 0.Source: §5.3 · p. 30
  • M_n = o(n log n) cannot produce an almost surely quasi-uniform nested sequence, even when the selection rule is arbitrary; the sharp budget order is n log n.A sufficiently large multiple of n log n suffices, while every subcritical budget fails almost surely.Source: §5.3 · pp. 29–30
  • Under supercritical budgets and α_n → 1, the nested construction has mesh-ratio limit superior 2 on compact positive-volume Euclidean domains.Source: §5.3 · p. 30

6 Numerical experiments

The experiments test random-covering and candidate-pool thresholds, approximate-FPS quality and cost, nested designs, and performance on nonrectangular domains. Across the tested settings, logarithmically oversampled pools produce bounded mesh ratios, while approximate search trades geometric quality for fewer distance evaluations.

6 Numerical experiments

  • Experiments used two-dimensional Euclidean domains with normalized area measure; the first four experiments used the unit square, and the last also used two nonrectangular domains.The reported medians and empirical 10%–90% bands summarize repetitions, and paired comparisons reused candidate streams where algorithms or budgets were compared.Source: §6 · p. 31

6.1 Random covering and the candidate-pool threshold

  • The normalized covering-radius median stayed between approximately 0.72 and 0.85 across the tested candidate-pool sizes, with a bounded empirical quantile band.This is consistent with the predicted random-covering order εM ≍P (log M/M)1/2.Source: §6.1 · p. 31, Figure 1 · p. 32
  • At N = 512, median mesh ratios were 3.02 for M = N log N, 2.38 for M = 4N log N, and 2.48 for M = N(log N)3/2.By comparison, M = N and M = 2N yielded medians of 151.6 and 5.05, respectively; growth for M = N√log N was not clearly visible over the tested range.Source: §6.1 · p. 32, Figure 2 · p. 33

6.2 Quality and cost of approximate FPS

  • At N = 1024, approximate-FPS mesh ratios increased from 2.39 for exact FPS to 4.46 at β = 2.00, while larger β reduced distance evaluations.At β = 1.25, 1.50, and 2.00, evaluation counts fell by factors of approximately 13, 23, and 38; MATLAB timings favored direct exact FPS in the tested range but were implementation-specific.Source: §6.2 · pp. 33–35, Figure 3 · p. 34

6.3 Nested randomized construction

  • At n = 2048, scaled covering and separation-radius medians were (0.95, 0.39) for the critical schedule and (0.92, 0.39) for the supercritical schedule.The subcritical schedule gave (1.59, 0.28), with a larger covering scale and smaller separation scale.Source: §6.3 · p. 35

6.4 Examples on nonrectangular domains

  • For the L-shaped domain and annulus, estimated mesh ratios were 2.442 and 2.198, with certified upper bounds of 2.547 and 2.375, respectively.The validation-set estimates can underestimate the true covering radius; the construction was also demonstrated on the square without a continuous largest-empty-ball solver or explicit domain Voronoi construction.Source: §6.4 · pp. 35–36

6.3 Nested randomized construction

  • At n = 2048, nested-design median mesh ratios were 5.70 for Mn = 2n, 2.46 for Mn = 4n log(n + 1), and 2.35 for Mn = 2n{log(n + 1)}3/2.The supercritical curve showed no clear tendency toward 2 over the tested prefix lengths; the authors note the asymptotic result concerns a limit superior, not monotone convergence.Source: §6.3 · p. 35, Figure 4 · p. 36

7 Concluding remarks

The paper establishes the sharp candidate-pool order for bounded mesh ratio and develops efficient and nested variants of the randomized FPS construction. It also identifies open questions on critical oversampling, candidate generation, and downstream error bounds.

7 Concluding remarks

  • M = Θ(N log N) is the sharp candidate-pool order for bounded mesh ratio: exact FPS achieves the upper bound with high probability, while every selector from the same iid pool faces a matching lower bound.The logarithmic oversampling requirement follows from the random covering properties of iid samples, not the greedy selection rule.Source: §7 · p. 36
  • Figure 5 depicts exact FPS designs with N = 500 from M = 12430 uniform iid candidates on the unit square, an L-shaped domain, and an annulus.The square mesh ratio is exact; the L-shaped-domain and annulus values are numerical estimates from dense validation sets.Source: Figure 5 · p. 37
  • At critical candidate size, the considered fast implementations have computational cost of order N log^2 N under the paper’s assumptions.Approximate FPS separates search error from candidate-set discretization error; bounded-doubling greedy-permutation algorithms are near-linear in pool size, and multiscale approximate FPS has a grid-based implementation on fixed-dimensional Euclidean domains.Source: §7 · pp. 36–37
  • Candidate budgets of order n log n yield an almost surely quasi-uniform nested sequence, and supercritical oversampling with asymptotically exact FPS gives lim sup mesh ratio at most 2.For compact positive-volume subsets of Euclidean space, this upper bound is optimal.Source: §7 · p. 37
  • Open questions concern the critical-regime dependence on the oversampling constant, candidate schemes beyond iid sampling, and links to quantitative downstream approximation or prediction errors.The paper also calls for a general theory connecting candidate-generation quality to subsequent FPS thinning.Source: §7 · p. 37

Funding

T.G. received support from a JSPS KAKENHI grant.

Funding

  • T.G. was supported by JSPS KAKENHI Grant Number JP26K00620.Source: Funding · p. 38

Declaration of AI use

The authors report using ChatGPT to assist with drafting, editing, and checking mathematical arguments and presentation.

Declaration of AI use

  • The authors used ChatGPT for portions of drafting and editing and for checking mathematical arguments and presentation, then critically reviewed, verified, and revised all AI-assisted content.Source: Declaration of AI use · p. 38
Loading 2609.05986v1…