Linear-size meshes

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}}