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.