Fast Sizing Calculations for Meshing

Provably correct algorithms for meshing difficult domains in three dimensions have been recently developed in the literature. These algorithms handle the problem of sharp angles (< π/2) between segments and between facets by constructing protective collars around these regions. The collars are approximately sized according to the local feature size of the input. With the eventual goal of developing time-efficient algorithms for the same mesh generation problems, we give a method for estimating the feature size of a 3D piecewise-linear-complex of size n on domain Ω in time O(n log Δ+m), where Δ is the spread of the input. The linear term m E O(∫_Ω 1/ lfs³) is bounded above by the output size of a quality generated mesh. Our algorithm is based on early termination of the Sparse-Voronoi- Refinement (SVR) meshing algorithm, which is not guaranteed to terminate in the presence of sharp angles.