Metraipolis › archive › dc_7d320362f6e2

Exact construction of quasi-uniform designs over polytopal domains — arXiv:2610.41592

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41592
License (as archived)
CC0-1.0
Archived
2026-11-03T05:44:17.626Z
SHA-256 of the archived text
f1b5b07897021b44b664e16506cceb74391c7847dd06fb2f57ba359334685db3
Stable URL of this page
https://metraipolis.com/documento/dc_7d320362f6e2

How to cite

Exact construction of quasi-uniform designs over polytopal domains — arXiv:2610.41592 — arXiv (en), https://arxiv.org/abs/2610.41592 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7d320362f6e2 (Metraipolis archive dc_7d320362f6e2, sha256 f1b5b07897021b44b664e16506cceb74391c7847dd06fb2f57ba359334685db3)
BibTeX
@misc{dc7d320362f6e2,
  title = {Exact construction of quasi-uniform designs over polytopal domains — arXiv:2610.41592},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41592},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7d320362f6e2; sha256 f1b5b07897021b44b664e16506cceb74391c7847dd06fb2f57ba359334685db3},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41592. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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(N\log N)$ unit-cost implementation and a separate implementation with $\widetilde O(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 $\Theta(N\log N)$ bit work, including exact quality measures at every prefix. Numerical experiments compare local Voronoi maintenance, coordinate growth, and direct generation.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.NA, nuovi lavori del giorno).
Categorie arXiv: Numerical Analysis (math.NA).
Pagina del lavoro: https://arxiv.org/abs/2610.41592 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T05:32:01.335Z dalla pagina https://arxiv.org/list/math.NA/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).