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},
  Pages = {175--178},
  Year = {2008}}