Constructive quasi-uniform sequences over triangles
This work addresses the need for efficient point generation in computational geometry and mesh generation, offering a practical solution with proven optimality, though it is incremental as it builds on existing concepts like Voronoi diagrams.
The paper tackled the problem of generating quasi-uniform point sets over triangular domains by developing a Voronoi-guided greedy packing algorithm, achieving a mesh ratio of at most 2, which is proven optimal, and demonstrated its efficiency in numerical experiments.
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.