New Bounds on the Size of Optimal Meshes
Donald R. Sheehy
In Computer Graphics Forum, 31(5), 2012.
Abstract: 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+nlogphi )$. 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 URL: http://dx.doi.org/10.1111/j.1467-8659.2012.03168.x
BibTeX format:
@article{Sheehy:2012:NBO,
  author = {Donald R. Sheehy},
  title = {New Bounds on the Size of Optimal Meshes},
  journal = {Computer Graphics Forum},
  volume = {31},
  number = {5},
  pages = {1627--1635},
  year = {2012},
}
Search for more articles by Donald R. Sheehy.

Return to the search page.


graphbib: Powered by "bibsql" and "SQLite3."