Premium
New Bounds on the Size of Optimal Meshes
Author(s) -
Sheehy Donald R.
Publication year - 2012
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2012.03168.x
Subject(s) - polygon mesh , dimension (graph theory) , mathematics , upper and lower bounds , matching (statistics) , point (geometry) , function (biology) , set (abstract data type) , domain (mathematical analysis) , feature (linguistics) , measure (data warehouse) , delaunay triangulation , computer science , algorithm , combinatorics , geometry , mathematical analysis , linguistics , statistics , philosophy , database , evolutionary biology , biology , programming language
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(ϕ d n ), where d is the input dimension. We give a new analysis of this integral showing that the output size is only θ( n + n logϕ). 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 ).