New Bounds on the Size of Optimal Meshes
Loading...
Date
2012
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and Blackwell Publishing Ltd.
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 Φ, then the number of vertices in an optimal mesh will be O(Φ<sup>d</sup>n), where d is the input dimension. We give a new analysis of this integral showing that the output size is only<br> θ(n+nlogΦ). 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).
Description
@article{10.1111:j.1467-8659.2012.03168.x,
journal = {Computer Graphics Forum},
title = {{New Bounds on the Size of Optimal Meshes}},
author = {Sheehy, Donald R.},
year = {2012},
publisher = {The Eurographics Association and Blackwell Publishing Ltd.},
ISSN = {1467-8659},
DOI = {10.1111/j.1467-8659.2012.03168.x}
}