Exact construction of quasi-uniform designs over polytopal domains
Abstract
We develop two sampling algorithms for constructing extensible designs with mesh ratio at most two on finite unions of full-dimensional rational convex polytopes. Starting from a rational initial point, both algorithms produce rational coordinates and perform the geometric comparisons governing point selection exactly. This ensures that distance ties and geometric degeneracies are handled without rounding ambiguity, preserving the prescribed selection rules and mesh-ratio guarantee at every stage. The first algorithm, Local Exact Farthest-Point Sampling (LEFPS), implements a prescribed farthest-point rule by local updates of the restricted Voronoi diagram. The second algorithm, Arithmetic-Aware Admissible Sampling (AAS), minimizes the representation length of reduced rational coordinates over admissible fragment vertices and edge midpoints. Since the cost of exact arithmetic depends on coordinate lengths, we analyze both operation counts and bit complexity. For fixed dimension and input, each sampling rule admits an O(Nlog N) unit-cost implementation and a separate implementation with Õ(LN) bit complexity, where LN is the total length of the output coordinates. On rational interval covers, every admissible sequence from the vertex-midpoint candidate set has logarithmic coordinate height. We also identify the ordered sequences explicitly for LEFPS on interval unions and four-dimensional coordinate-order domains, and for AAS on a rectangle and a nonconvex cross. These descriptions yield direct generation with O(N) unit-cost work and optimal Θ(Nlog N) bit work, including exact quality measures at every prefix. Numerical experiments compare local Voronoi maintenance, coordinate growth, and direct generation.
Related
- A General Superconvergence Result for Cubature on Tesselated Polytopal Domains in Two and Three Dimensions
- A construction of spherical 5-designs with O(d2) points
- A sharp bound for sampling widths in the uniform norm: kernel D-optimal designs and oversampling
- A Method of Construction of Pairwise Additive Balanced Incomplete Block Designs
- Greedy sampling designs via reduced basis methods: optimal recovery in the uniform norm
BibTeX
@misc{yang2026exact,
title = {{Exact construction of quasi-uniform designs over polytopal domains}},
author = {Songlin Yang and Takashi Goda},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41592},
eprint = {2610.41592},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41592},
}
RIS
TY - UNPB
TI - Exact construction of quasi-uniform designs over polytopal domains
AU - Songlin Yang
AU - Takashi Goda
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41592
UR - https://arxiv.org/abs/2610.41592
AB - We develop two sampling algorithms for constructing extensible designs with mesh ratio at most two on finite unions of full-dimensional rational convex polytopes. Starting from a rational initial point, both algorithms produce rational coordinates and perform the geometric comparisons governing point selection exactly. This ensures that distance ties and geometric degeneracies are handled without rounding ambiguity, preserving the prescribed selection rules and mesh-ratio guarantee at every stage. The first algorithm, Local Exact Farthest-Point Sampling (LEFPS), implements a prescribed farthest-point rule by local updates of the restricted Voronoi diagram. The second algorithm, Arithmetic-Aware Admissible Sampling (AAS), minimizes the representation length of reduced rational coordinates over admissible fragment vertices and edge midpoints. Since the cost of exact arithmetic depends on coordinate lengths, we analyze both operation counts and bit complexity. For fixed dimension and input, each sampling rule admits an O(Nlog N) unit-cost implementation and a separate implementation with Õ(L_N) bit complexity, where L_N is the total length of the output coordinates. On rational interval covers, every admissible sequence from the vertex-midpoint candidate set has logarithmic coordinate height. We also identify the ordered sequences explicitly for LEFPS on interval unions and four-dimensional coordinate-order domains, and for AAS on a rectangle and a nonconvex cross. These descriptions yield direct generation with O(N) unit-cost work and optimal Θ(Nlog N) bit work, including exact quality measures at every prefix. Numerical experiments compare local Voronoi maintenance, coordinate growth, and direct generation.
ER -