file.pdf (140.93 kB)

Linear-Size Meshes

Download (140.93 kB)
journal contribution
posted on 01.04.1998, 00:00 by Gary L. Miller, Todd Phillips, Donald Sheehy
Most modern meshing algorithms produce asymptoti- cally optimal size output. However, the size of the opti- mal mesh may not be bounded by any function of n. In this paper, we introduce 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 bal- ancing quadtrees. We also present an algorithm that uses well-paced points to produce a linear size Delau- nay mesh of a point set in Rd