New Bounds on the Size of Optimal Meshes
| dc.contributor.author | Sheehy, Donald R. | en_US |
| dc.contributor.editor | Eitan Grinspun and Niloy Mitra | en_US |
| dc.date.accessioned | 2015-02-28T07:44:08Z | |
| dc.date.available | 2015-02-28T07:44:08Z | |
| dc.date.issued | 2012 | en_US |
| dc.description.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). | en_US |
| dc.description.seriesinformation | Computer Graphics Forum | en_US |
| dc.description.volume | 31 | |
| dc.identifier.doi | 10.1111/j.1467-8659.2012.03168.x | |
| dc.identifier.issn | 1467-8659 | en_US |
| dc.identifier.uri | https://doi.org/10.1111/j.1467-8659.2012.03168.x | en_US |
| dc.publisher | The Eurographics Association and Blackwell Publishing Ltd. | en_US |
| dc.subject | F.2.2 [Analysis of Algorithms and Problem Complexity] | en_US |
| dc.subject | Nonnumerical Algorithms and Problems | en_US |
| dc.subject | Geometrical problems and computations | en_US |
| dc.title | New Bounds on the Size of Optimal Meshes | en_US |