pith. sign in

arxiv: 2511.07909 · v2 · submitted 2025-11-11 · 🧮 math.NA · cs.NA

Constructive quasi-uniform sequences over triangles

Hengjun Xu , Takashi Goda This is my paper

Pith reviewed 2026-05-18 00:13 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords quasi-uniform point setsVoronoi diagramgreedy packingmesh ratiotriangular domainslow-discrepancy sequencesconstructive algorithms
0
0 comments X

The pith

Voronoi-guided greedy packing on any triangle reaches mesh ratio at most 2 after finite steps.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops constructive algorithms that generate quasi-uniform point sets on arbitrary triangles. Its main algorithm, called Voronoi-guided greedy packing, repeatedly chooses the farthest point from a finite list of candidates taken from the current Voronoi diagram. The central theorem states that this procedure produces a point set whose mesh ratio is at most 2 after only finitely many additions, matching the known optimal bound. The work also proves that two standard low-discrepancy constructions on triangles have mesh ratios bounded uniformly for every number of points. Numerical tests illustrate that the method runs efficiently and yields high-quality distributions in practice.

Core claim

The Voronoi-guided greedy packing algorithm iteratively selects the point farthest from the current set among candidates extracted from the Voronoi diagram of the triangle; after a finite number of iterations the mesh ratio of the resulting point set is at most 2, which is optimal.

What carries the argument

Voronoi-guided greedy packing, which builds a finite candidate set from the Voronoi diagram of the current points and greedily adds the candidate that maximizes the minimum distance to existing points.

If this is right

  • Quasi-uniform point sets with the optimal mesh ratio can be constructed algorithmically for every given triangle.
  • The sequences are suitable for numerical integration or sampling tasks that require even distribution inside a triangle.
  • Two common low-discrepancy constructions on triangles are now known to be quasi-uniform because their mesh ratios remain bounded.
  • The constructive procedure supplies an efficient practical generator of high-quality point sets on individual triangles.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same Voronoi-candidate selection idea could be tested on other polygonal domains to see whether a similar finite bound on mesh ratio holds.
  • Point sets with guaranteed mesh ratio 2 may improve error constants in quadrature or finite-element schemes restricted to triangular regions.
  • The finite convergence property might be used to derive explicit constructions for low-discrepancy sequences on triangles without external optimization.

Load-bearing premise

The finite candidate set extracted from the Voronoi diagram always contains a point that advances the mesh ratio toward the global optimum without trapping the greedy process in a configuration whose ratio exceeds 2.

What would settle it

A concrete triangle together with a sequence of points chosen by the algorithm for which the mesh ratio exceeds 2 after any finite number of additions.

Figures

Figures reproduced from arXiv: 2511.07909 by Hengjun Xu, Takashi Goda.

Figure 1
Figure 1. Figure 1: Example of point sets generated by the VG algorithm from n = 3 to n = 11. In each subplot, the blue dots denote the generated points, the dashed lines denote the Voronoi edges, and the orange dots denote the candidate set. Lemma 3.2. Let T = △ABC be a non-degenerate triangle, and let (xi)i≥1 be the sequence of points generated by Algorithm 2. Denote Pn = {x1, . . . , xn}. Then the following statements hold… view at source ↗
Figure 2
Figure 2. Figure 2: Mesh ratio of point sets generated by the VG algorithm for various isoperimetric quotients J, shown for n = 10 (red), n = 20 (orange), and n = 50 (blue). of points increases. Finally, we assess their performance in a radial basis function (RBF) interpolation task. 4.1. Geometric sensitivity of the VG algorithm. We study how the shape of a triangle affects the mesh ratio. To eliminate scale effects, the tri… view at source ↗
Figure 3
Figure 3. Figure 3: Number of points required for the VG algorithm to achieve the optimal mesh ratio of 2, comparing empirical results (orange) with theoretical bounds (blue). We know from Theorem 3.3 that the number of points required for the VG algorithm to achieve the optimal mesh ratio of 2 is at most  AT + LT q(P3; T) + π q(P3; T) 2 π q(P3; T) 2  + 1. We compare this theoretical bound with the empirical result. The emp… view at source ↗
Figure 4
Figure 4. Figure 4: Six point sets with n = 45: our VG algorithm (left top), barycentric grid (middle top), triangular van der Corput sequence (right top), triangular Kronecker lattice (left bottom), PD random (middle bottom), and i.i.d. random (right bottom). Our barycentric grid point set is generated using a hybrid approach. First, we construct a uniform barycentric lattice with m divisions per side, where m is chosen to c… view at source ↗
Figure 5
Figure 5. Figure 5: Mesh ratio of six point sets in the unit equilateral tri￾angle: our VG algorithm (blue), barycentric grid (green), triangu￾lar van der Corput sequence (orange), triangular Kronecker lattice (red), PD random (black dash), and i.i.d. random (black). lower bound for several n. This indicates that the VG algorithm effectively sup￾presses local voids and maintains a near-optimal quasi-uniformity, demonstrating … view at source ↗
Figure 6
Figure 6. Figure 6: Mesh ratio of six point sets in a skinny triangle with vertices (0, 0),(1, 0),(0.028, 0.045): our VG algorithm (blue), barycentric grid (green), triangular van der Corput sequence (or￾ange), triangular Kronecker lattice (red), PD random (black dash), and i.i.d. random (black). However, its mesh ratio increases gradually, suggesting it will perform worse than the deterministic, constructive sets for larger … view at source ↗
Figure 7
Figure 7. Figure 7: RBF interpolation of the Franke function (Gaussian kernel, n = 45): true surface (top), our VG algorithm (middle left), barycentric grid (middle center), triangular van der Corput sequence (middle right), triangular Kronecker lattice (bottom left), PD random (bottom center), and i.i.d. random (bottom right). c = 5 in the bottom-left and -right plots. Obviously, different values of c can lead to different a… view at source ↗
Figure 8
Figure 8. Figure 8: Convergence behavior of the RBF interpolation RMSE (E2) for various test functions and kernels: Franke with Gauss￾ian kernel (top left), Fourier2d with Gaussian kernel (top right), Franke with Mat´ern–5/2 kernel (middle left), Fourier2d with Mat´ern–5/2 kernel (middle right), ridge with Wendland-C 2 ker￾nel (bottom left), and runge with Wendland-C 2 kernel (bottom right). Different colors represent differe… view at source ↗
read the original abstract

In this paper, we develop constructive algorithms for generating quasi-uniform point sets and sequences over arbitrary two-dimensional triangular domains. Our proposed method, called the \emph{Voronoi-guided greedy packing} algorithm, iteratively selects the point farthest from the current set among a finite candidate set determined by the Voronoi diagram of the triangle. Our main theoretical result shows that, after a finite number of iterations, the mesh ratio of the generated point set is at most~2, which is known to be optimal. We further analyze two existing triangular low-discrepancy point sets and prove that their mesh ratios are uniformly bounded, thereby establishing their quasi-uniformity. Finally, through a series of numerical experiments, we demonstrate that the proposed method provides an efficient and practical strategy for generating high-quality point sets on individual triangles.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript develops a Voronoi-guided greedy packing algorithm that iteratively inserts points into a triangular domain by selecting the farthest candidate from a finite set extracted from the current Voronoi diagram. The central theoretical claim is that after finitely many iterations the mesh ratio μ = h/s of the generated point set satisfies μ ≤ 2, which is optimal. The paper additionally proves that two existing low-discrepancy triangular point sets have uniformly bounded mesh ratios and reports numerical experiments on efficiency and quality.

Significance. If the finite-iteration bound holds, the algorithm supplies a constructive, deterministic procedure that achieves the known optimal mesh ratio on arbitrary triangles, which is directly useful for mesh generation, quadrature rules, and sampling in numerical PDE solvers. The boundedness results for existing sets also strengthen the literature on quasi-uniformity over triangles.

major comments (2)
  1. [§4, Theorem 4.1] §4, Theorem 4.1 (finite-iteration proof): the argument that the greedy step always produces a point with insertion distance d ≥ 2s whenever the current μ > 2 assumes the finite Voronoi-derived candidate set contains a global maximizer of min-distance to the existing sites. It is not shown that this set includes all Voronoi-edge maximizers and all boundary points of the triangle; without this, the proof does not rule out insertion of a point with d < 2s that fails to decrease μ below 2.
  2. [§3.1] §3.1 (candidate-set construction): when the triangle is obtuse or has high aspect ratio, the location that maximizes min-distance to the current point set can lie on a Voronoi edge or on the boundary rather than at a Voronoi vertex. The manuscript must explicitly verify that the extracted finite candidate list contains such points, otherwise the claimed descent property does not hold for all admissible triangles.
minor comments (2)
  1. [§2] The notation h (covering radius) and s (minimum separation) is introduced only in the abstract and should be defined at the beginning of §2 with the mesh-ratio definition.
  2. [§5] Numerical tables in §5 would be clearer if each row also reported the number of iterations required to reach μ ≤ 2.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The comments identify important clarifications needed in the candidate-set construction and the finite-iteration proof. We address each point below and will revise the manuscript to make the arguments fully rigorous.

read point-by-point responses

  1. Referee: [§4, Theorem 4.1] §4, Theorem 4.1 (finite-iteration proof): the argument that the greedy step always produces a point with insertion distance d ≥ 2s whenever the current μ > 2 assumes the finite Voronoi-derived candidate set contains a global maximizer of min-distance to the existing sites. It is not shown that this set includes all Voronoi-edge maximizers and all boundary points of the triangle; without this, the proof does not rule out insertion of a point with d < 2s that fails to decrease μ below 2.

    Authors: We appreciate this observation on the completeness of the descent argument. The manuscript constructs the candidate set from the Voronoi diagram of the current sites clipped to the triangle, but the current text does not contain an explicit lemma verifying that this finite set always includes a point achieving the global maximum min-distance (including on edges and boundaries). We will add such a lemma in the revised Section 3, together with a precise characterization of the extracted points, thereby closing the gap and ensuring Theorem 4.1 holds for arbitrary triangles. revision: yes

  2. Referee: [§3.1] §3.1 (candidate-set construction): when the triangle is obtuse or has high aspect ratio, the location that maximizes min-distance to the current point set can lie on a Voronoi edge or on the boundary rather than at a Voronoi vertex. The manuscript must explicitly verify that the extracted finite candidate list contains such points, otherwise the claimed descent property does not hold for all admissible triangles.

    Authors: We agree that the maximizer of min-distance can occur on a Voronoi edge or on the boundary when the triangle is obtuse or has large aspect ratio. Our algorithmic description in §3.1 intends to include such locations by sampling appropriate points on the relevant Voronoi edges and triangle sides, but this is not stated with sufficient precision. In the revision we will expand §3.1 with an explicit enumeration of the candidate-generation rules (including boundary and edge cases), a short proof that the selected finite list contains a sufficiently distant point, and, if helpful, a small illustrative figure. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation of mesh ratio bound

full rationale

The paper defines the Voronoi-guided greedy packing algorithm and states that its iterative selection from Voronoi-derived candidates produces mesh ratio μ ≤ 2 after finitely many steps, with 2 noted as known to be optimal. This claim rests on the geometric construction of the candidate set and the greedy rule rather than any self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. No equations or steps in the provided text reduce the target bound to the algorithm's inputs by construction; the result is presented as a theorem proved from the algorithm's properties. The derivation is therefore self-contained against external benchmarks for the stated optimality.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard properties of Voronoi diagrams inside triangles and the definition of mesh ratio; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Voronoi diagrams of finite point sets inside a triangle yield a finite set of candidate locations sufficient for greedy farthest-point selection.
    Invoked when the algorithm restricts choices to Voronoi-derived candidates.

pith-pipeline@v0.9.0 · 5423 in / 1290 out tokens · 41337 ms · 2026-05-18T00:13:59.231652+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · 1 internal anchor

  1. [1]

    Babuˇ ska and A

    I. Babuˇ ska and A. K. Aziz,On the angle condition in the finite element method, SIAM J. Numer. Anal.13(1976), no. 2, 214–226

    work page 1976

  2. [2]

    Owen,Low discrepancy constructions in the triangle, SIAM J

    Kinjal Basu and Art B. Owen,Low discrepancy constructions in the triangle, SIAM J. Numer. Anal.53(2015), no. 2, 743–761

    work page 2015

  3. [3]

    Ciarlet,The finite element method for elliptic problems, Studies in Mathemat- ics and its Applications, vol

    Philippe G. Ciarlet,The finite element method for elliptic problems, Studies in Mathemat- ics and its Applications, vol. Vol. 4, North-Holland Publishing Co., Amsterdam-New York- Oxford, 1978

    work page 1978

  4. [4]

    Stefano De Marchi and Robert Schaback,Stability of kernel-based interpolation, Adv. Comput. Math.32(2010), no. 2, 155–161

    work page 2010

  5. [5]

    Josef Dick, Takashi Goda, Gerhard Larcher, Friedrich Pillichshammer, and Kosuke Suzuki, On the quasi-uniformity properties of quasi-Monte Carlo lattice point sets and sequences, 2025, arXiv:2502.06202,https://arxiv.org/abs/2502.06202

    work page arXiv 2025

  6. [6]

    Josef Dick, Takashi Goda, and Kosuke Suzuki,On the quasi-uniformity properties of quasi- Monte Carlo digital nets and sequences, 2025, arXiv:2501.18226,https://arxiv.org/abs/ 2501.18226

    work page arXiv 2025

  7. [7]

    Gracia Yunruo Dong, Erik Hintz, Marius Hofert, and Christiane Lemieux,Randomized quasi– Monte Carlo methods on triangles: extensible lattices and sequences, Methodol. Comput. Appl. Probab.26(2024), no. 2, Paper No. 15, 31

    work page 2024

  8. [8]

    Graph.25(2006), no

    Daniel Dunbar and Greg Humphreys,A spatial data structure for fast Poisson-disk sample generation, ACM Trans. Graph.25(2006), no. 3, 503–508

    work page 2006

  9. [9]

    Kai-Tai Fang, Runze Li, and Agus Sudjianto,Design and modeling for computer experiments, Chapman & Hall/CRC Computer Science and Data Analysis Series, Chapman & Hall/CRC, Boca Raton, FL, 2006

    work page 2006

  10. [10]

    1, 153– 174

    S Fortune,A sweepline algorithm for Voronoi diagrams, Algorithmica2(1987), no. 1, 153– 174

    work page 1987

  11. [11]

    Takashi Goda,One-dimensional quasi-uniform Kronecker sequences, Arch. Math. (Basel)123 (2024), no. 5, 499–505

    work page 2024

  12. [12]

    ,The Sobol’ sequence is not quasi-uniform in dimension 2, Proc. Amer. Math. Soc. 152(2024), no. 8, 3209–3213

    work page 2024

  13. [13]

    Takashi Goda, Kosuke Suzuki, and Takehito Yoshiki,Quasi-Monte Carlo integration for twice differentiable functions over a triangle, J. Math. Anal. Appl.454(2017), no. 1, 361–384

    work page 2017

  14. [14]

    D. P. Hardin, T. Michaels, and E. B. Saff,A comparison of popular point configurations on S2, Dolomites Res. Notes Approx.9(2016), no. 1, 16–49

    work page 2016

  15. [15]

    M. E. Johnson, L. M. Moore, and D. Ylvisaker,Minimax and maximin distance designs, J. Statist. Plann. Inference26(1990), no. 2, 131–148

    work page 1990

  16. [16]

    Roshan Joseph,Space-filling designs for computer experiments: A review, Qual

    V. Roshan Joseph,Space-filling designs for computer experiments: A review, Qual. Eng.28 (2016), no. 1, 28–35

    work page 2016

  17. [17]

    Leif Kobbelt, Swen Campagna, and Hans-Peter Seidel,A general framework for mesh deci- mation, Proceedings of the Graphics Interface 1998 Conference, June 18-20, 1998, Vancouver, BC, Canada, 1998, pp. 43–50

    work page 1998

  18. [18]

    Kuipers and H

    L. Kuipers and H. Niederreiter,Uniform distribution of sequences, Pure and Applied Mathe- matics, Wiley-Interscience, New York-London-Sydney, 1974

    work page 1974

  19. [19]

    Larsson and B

    E. Larsson and B. Fornberg,A numerical study of some radial basis function based solution methods for elliptic PDEs, Comput. Math. Appl.46(2003), no. 5-6, 891–902

    work page 2003

  20. [20]

    63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992

    Harald Niederreiter,Random number generation and quasi-Monte Carlo methods, CBMS- NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992

    work page 1992

  21. [21]

    Erich Novak,Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, Springer Berlin, Heidelberg, 1988

    work page 1988

  22. [22]

    Pronzato and A

    L. Pronzato and A. Zhigljavsky,Quasi-uniform designs with optimal and near-optimal uni- formity constant, J. Approx. Theory294(2023), Paper No. 105931, 14

    work page 2023

  23. [23]

    M¨ uller,Design of computer experiments: space filling and beyond, Stat

    Luc Pronzato and Werner G. M¨ uller,Design of computer experiments: space filling and beyond, Stat. Comput.22(2012), no. 3, 681–701

    work page 2012

  24. [24]

    Santner, Brian J

    Thomas J. Santner, Brian J. Williams, and William I. Notz,The design and analysis of computer experiments, Springer Series in Statistics, Springer-Verlag, New York, 2003. 28 HENGJUN XU AND TAKASHI GODA

    work page 2003

  25. [25]

    Robert Schaback,Error estimates and condition numbers for radial basis function interpola- tion, Adv. Comput. Math.3(1995), no. 3, 251–264

    work page 1995

  26. [26]

    Robert Schaback and Holger Wendland,Kernel techniques: from machine learning to mesh- less methods, Acta Numer.15(2006), 543–639

    work page 2006

  27. [27]

    Schroeder, Jonathan A

    William J. Schroeder, Jonathan A. Zarge, and William E. Lorensen,Decimation of triangle meshes, Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’92), ACM, 1992, pp. 65–70

    work page 1992

  28. [28]

    Indexing the Sphere with the Hierarchical Triangular Mesh

    Alexander S. Szalay, Jim Gray, George Fekete, Peter Z. Kunszt, Peter Kukol, and Ani Thakar, Indexing the sphere with the hierarchical triangular mesh, 2007, arXiv:cs/0701164,https: //arxiv.org/abs/cs/0701164

    work page internal anchor Pith review Pith/arXiv arXiv 2007

  29. [29]

    17, Cambridge University Press, Cambridge, 2005

    Holger Wendland,Scattered data approximation, Cambridge Monographs on Applied and Computational Mathematics, vol. 17, Cambridge University Press, Cambridge, 2005

    work page 2005

  30. [30]

    Wenzel, G

    T. Wenzel, G. Santin, and B. Haasdonk,A novel class of stabilized greedy kernel approxi- mation algorithms: Convergence, stability and uniform point distribution, J. Approx. Theory 262(2021), Paper No. 105508, 30. Graduate School of Engineering, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan Email address:jokokun@g.ecc.u-tokyo.ac.j...

    work page 2021