Mesh Size Analysis and the Scaffold Theorem
January 14, 2009
Like scaffolding in office building construction, iterative meshing
algorithms typically bootstrap by constructing extraneous vertices
(scaffolding) within a bounding box larger than the region of
interest. These scaffold vertices are then discarded at output. The
Scaffold Theorem guarantees that this cost is dominated by the output
of interest and is thus negligible. I will develop the ideas of
well-paced orderings and well-spaced supersets of points that lead to
the proof of the Scaffold theorem and show how this improves the
runtime bounds for several state of the art meshing algorithms.