New Bounds on the Size of Optimal Meshes

Computer Graphics Forum, 31:5, 1627-1635
2012

The theory of optimal size meshes gives a method for analyzing the output size (number of simplices) of a Delaunay refinement mesh in terms of the integral of a sizing function over the input domain.
The input points define a maximal such sizing function called the feature size.
This paper presents a way to bound the feature size integral in terms of an easy to compute property of a suitable ordering of the point set.
The key idea is to consider the pacing of an ordered point set, a measure of the rate of change in the feature size as points are added one at a time.
In previous work, Miller et al.\ showed that if an ordered point set has pacing $\phi$, then the number of vertices in an optimal mesh will be $O(\phi^dn)$, where $d$ is the input dimension.
We give a new analysis of this integral showing that the output size is only $\Theta(n + n\log \phi)$.
The new analysis tightens bounds from several previous results and provides matching lower bounds.
Moreover, it precisely characterizes inputs that yield outputs of size $O(n)$.

@article{sheehy12new, Title = {{New Bounds on the Size of Optimal Meshes}}, Author = {Donald R. Sheehy}, Journal = {Computer Graphics Forum}, Volume= {31}, Number= {5}, Pages = {1627--1635}, Year = {2012}}