Linear-size meshes
Gary L. Miller, Todd Phillips and Donald R. Sheehy
CCCG: The Canadian Conference in Computational Geometry 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 \emph{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$.
@inproceedings{miller08linear,
Author = {Gary L. Miller and Todd Phillips and Donald R. Sheehy},
Booktitle = {CCCG: Canadian Conference in Computational Geometry},
Title = {Linear-size meshes},
Year = {2008}}