Linear-size meshes
CCCG: The Canadian Conference in Computational Geometry, 2008
Abstract
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$.
Files