Linear-Size Meshes
Gary Lee Miller, Todd W. Phillips, Donald R. Sheehy · 2008
Most modern meshing algorithms produce asymptotically optimal size output. However, the size of the optimal mesh may not be bounded by any function of n. In this paper, we introduce well-paced point sets and prove that these will produce linear size outputs when meshed with any “size-optimal ” meshing algorithm. This work generalizes all previous work on the linear cost of balancing quadtrees. We also present an algorithm that uses well-paced points to produce a linear size Delaunay mesh of a point set in R d. 1