🔢 mathematics

Constructive quasi-uniform sequences over triangles

This paper introduces a constructive "Voronoi-guided greedy packing" algorithm that generates quasi-uniform point sets on arbitrary triangular domains with an optimal mesh ratio of at most 2, while also proving the quasi-uniformity of existing low-discrepancy sets and validating the method's efficiency through numerical experiments.

Original authors: Hengjun Xu, Takashi Goda

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hengjun Xu, Takashi Goda

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a landscape architect tasked with placing sprinklers in a triangular garden. Your goal is simple: you want every drop of water to reach every corner of the grass, but you also want to make sure no two sprinklers are spraying the same spot (wasting water) or standing too close together (causing a flood).

This is exactly the problem mathematicians Hengjun Xu and Takashi Goda are solving in their paper. They are figuring out how to place points (like sprinklers) inside a triangle so that the distribution is perfectly balanced.

Here is the breakdown of their work using simple analogies:

1. The Problem: The "Goldilocks" Distribution

In math and engineering, we often need to sample a shape (like a triangle) with points to do calculations (like predicting weather or simulating airflow).

Too Clumped: If points are bunched up in one corner, you miss the rest of the triangle.
Too Spread Out: If points are too far apart, you leave huge "dead zones" where nothing is measured.
The Sweet Spot: You want points that are evenly spaced (no clumps) but also completely covering (no gaps).

The authors call this "Quasi-Uniformity." Think of it like a well-organized army formation: everyone has their own personal space, but the formation covers the entire battlefield without leaving holes.

2. The Old Ways vs. The New Way

Before this paper, people used a few methods to place these points:

Random Sprinkling: Like throwing darts blindfolded. Sometimes you get lucky, but often you get clumps and huge gaps.
Low-Discrepancy Sequences: These are fancy, pre-calculated patterns (like a grid) that look very even. However, the authors found a catch: Just because a pattern looks "low discrepancy" (mathematically smooth) doesn't mean it's "quasi-uniform" (geometrically perfect). Some of these patterns have tiny gaps or points that are dangerously close together, which can break computer simulations.
The "Greedy" Approach: Imagine you are placing sprinklers one by one. After placing the first few, you look at the biggest dry patch in the garden and put the next sprinkler right in the middle of that dry patch. This is called "Greedy Packing." It works great, but calculating exactly where the biggest dry patch is can be incredibly hard and slow for a computer, especially in a weirdly shaped triangle.

3. The Solution: The "Voronoi-Guided" Algorithm

The authors invented a new method called the Voronoi-Guided Greedy Packing (VG) Algorithm.

The Analogy:
Imagine the triangle is a room, and the points you've already placed are people standing in it.

The Voronoi Diagram: This is a map that divides the room into territories. Every spot in the room belongs to the person standing closest to it. If you draw lines between these territories, you get a spiderweb pattern.
The Magic Trick: The authors realized that the "biggest dry patch" (the worst place to be) can only be found at specific, easy-to-calculate spots on this spiderweb: either where three lines meet (a vertex) or where a line hits the wall.
The Algorithm: Instead of scanning the whole room to find the dry spot, the computer just looks at these specific "checkpoints" on the spiderweb, picks the one that is farthest from everyone, and places a new point there.

Why it's a big deal:

It's Fast: It turns a super-hard math problem into a simple checklist.
It's Perfect: They proved mathematically that no matter how weird the triangle is (even a long, skinny one), this method will eventually create a pattern where the "gap-to-clump" ratio is at most 2. This is the theoretical "Goldilocks" limit—the best you can possibly do.

4. The Results: Why Should You Care?

The authors tested their method against the old ways (random points, fancy grids, and low-discrepancy sequences) using computer simulations.

The "Skinny Triangle" Test: They used a very long, thin triangle (like a slice of pizza crust).
- Old methods: Failed miserably. They left huge gaps or clumped points together.
- VG Algorithm: Handled it perfectly, filling the thin strip evenly.
The Interpolation Test: They used these points to guess the shape of a bumpy surface (like a mountain range).
- The VG algorithm and a standard grid were the most accurate.
- The "low-discrepancy" sequences (which usually get high praise) actually performed worse because their points weren't spaced out evenly enough to handle the bumps.

The Takeaway

This paper gives us a new, reliable "recipe" for placing points in triangular shapes. Whether you are designing a video game map, simulating airflow over a wing, or modeling the spread of a disease, you need your data points to be perfectly balanced.

The authors' Voronoi-Guided algorithm is like a smart gardener who knows exactly where to plant the next flower to ensure the whole garden looks beautiful, no matter how weird the shape of the plot is. It's fast, it's provably the best it can be, and it works where other methods fail.

1. Problem Statement

The paper addresses the challenge of generating high-quality point sets and sequences over arbitrary two-dimensional triangular domains. In computational mathematics (e.g., interpolation, scattered data approximation, and physical simulations), the accuracy and stability of algorithms depend heavily on the distribution of sampling nodes.

Quasi-Uniformity: The quality of a point set is measured by its mesh ratio ( $\rho$ ), defined as the ratio of the covering radius ( $h$ , the maximum distance from any point in the domain to the nearest node) to the separation radius ( $q$ , half the minimum distance between any two nodes). A small mesh ratio implies both good coverage and well-separated points.
The Gap: While optimal quasi-uniform sequences (with a mesh ratio bounded by 2) are known for symmetric domains like the unit hypercube or sphere, constructing them for arbitrary triangles is difficult. Triangles often exhibit asymmetry and boundary anisotropy (e.g., "skinny" triangles), making standard lattice-based or low-discrepancy methods suboptimal or unstable.
Low-Discrepancy vs. Quasi-Uniformity: The authors highlight that low-discrepancy sequences (often used in Quasi-Monte Carlo methods) do not necessarily possess low mesh ratios. A set can have low discrepancy but poor separation (clustering), leading to numerical instability in kernel interpolation.

2. Methodology

The paper proposes a constructive algorithm and provides theoretical analyses of existing methods.

A. The Voronoi-Guided Greedy Packing (VG) Algorithm

The primary contribution is a new constructive algorithm designed to generate extensible quasi-uniform sequences on triangles.

Concept: It is a constructive version of the "simple greedy packing" algorithm, which iteratively selects the point farthest from the current set (maximizing the covering radius).
Implementation Challenge: Finding the exact farthest point in a continuous domain is computationally hard.
VG Solution: The authors leverage the Voronoi diagram of the current point set. They prove (via Lemma 2.8) that the point attaining the covering radius must lie at one of a finite set of candidates:
1. Voronoi vertices inside the triangle.
2. Intersections of Voronoi edges with the triangle boundary.
3. The triangle's own vertices.
Procedure:
1. Initialize with the three vertices of the triangle ( $P_3 = \{A, B, C\}$ ).
2. Compute the Voronoi diagram of the current set.
3. Identify the finite candidate set $C_n$ .
4. Select the next point $x_{n+1}$ from $C_n$ that maximizes the distance to the current set.
5. Repeat.
Complexity: Using incremental updates and priority queues, the algorithm can generate $N$ points in $O(N \log N)$ time.

B. Analysis of Existing Methods

The paper also analyzes two existing triangular low-discrepancy constructions to determine if they are quasi-uniform:

Triangular van der Corput Sequence: A digital construction based on recursive subdivision of triangles into four congruent sub-triangles.
Triangular Kronecker Lattices: Constructed by mapping a rotated and scaled integer lattice onto the triangle via an affine transformation.

3. Key Contributions and Theoretical Results

1. Optimal Mesh Ratio Bound for VG Algorithm

The main theoretical result (Theorem 3.3) proves that the VG algorithm generates a sequence where the mesh ratio is uniformly bounded by 2 after a finite number of iterations.

Optimality: A mesh ratio of 2 is known to be the theoretical lower bound for extensible sequences in arbitrary compact domains (proven by Pronzato and Zhigljavsky).
Convergence: Even if the initial triangle is "skinny" (resulting in a high initial mesh ratio), the algorithm is guaranteed to converge to $\rho \le 2$ within a calculable number of steps ( $K$ ), which depends on the triangle's area, perimeter, and initial separation.
Geometric Property: The algorithm ensures that the angles of the Delaunay triangles formed by the points are bounded away from zero, preventing ill-conditioned interpolation matrices.

2. Quasi-Uniformity of Existing Low-Discrepancy Sets

Triangular van der Corput: The authors prove these sets are quasi-uniform (mesh ratio is bounded), but the bound depends on the triangle's geometry (specifically the ratio of medians and side lengths). For equilateral triangles, the bound is optimal ( $2/\sqrt{3}$ ), but for skewed triangles, the bound can exceed 2.
Triangular Kronecker Lattices: These are proven to be quasi-uniform as a sequence of point sets. However, their mesh ratio bound is amplified by the condition number of the affine map transforming the reference triangle to the target triangle. This means highly anisotropic (skinny) triangles will have significantly worse mesh ratios with this method.

4. Numerical Results

The authors conducted extensive experiments comparing the VG algorithm against:

Triangular van der Corput sequence
Triangular Kronecker lattice
Barycentric grids
Random point sets (i.i.d. and Poisson-disk)

Key Findings:

Geometric Sensitivity: The VG algorithm is robust across various triangle shapes. While "skinny" triangles initially yield higher mesh ratios, the ratio converges to the optimal bound of 2 as $n$ increases.
Mesh Ratio Performance:
- VG Algorithm: Consistently achieves $\rho \le 2$ and often approaches the theoretical minimum ( $2/\sqrt{3}$ ) for equilateral triangles. It outperforms all other methods, especially on degenerate (skinny) triangles.
- Low-Discrepancy Sets: The van der Corput sequence and Kronecker lattices are stable but often exhibit higher mesh ratios than VG, particularly on non-equilateral triangles. This confirms that low discrepancy does not guarantee quasi-uniformity.
- Random Sets: Perform the worst, with mesh ratios increasing or fluctuating significantly.
RBF Interpolation: In Radial Basis Function (RBF) interpolation tasks (using Franke, Fourier, ridge, and Runge functions), the VG algorithm and barycentric grids demonstrated superior accuracy and stability compared to low-discrepancy and random sets. This validates the practical importance of maintaining a small mesh ratio for numerical stability.

5. Significance

Theoretical Advancement: The paper bridges the gap between greedy packing theory and practical implementation on non-symmetric domains, providing the first constructive algorithm with a provable optimal mesh ratio bound for arbitrary triangles.
Practical Utility: The VG algorithm offers a reliable strategy for generating sampling nodes in fields like Finite Element Analysis (FEA), Computational Fluid Dynamics (CFD) (where boundary layers require skinny triangles), and Computer Graphics.
Clarification of Concepts: It rigorously demonstrates that low-discrepancy and quasi-uniformity are distinct properties; relying solely on low-discrepancy sequences for interpolation on complex domains can lead to numerical instability.
Extensibility: Unlike one-shot generation methods, the VG algorithm produces an extensible sequence, allowing users to add points dynamically without recomputing the entire set, which is crucial for adaptive refinement strategies.