The minimum feature size of a planar straight-line graph is the minimum distance between a vertex and a nonincident edge. When such a graph is partitioned into a mesh, the degradation is the ratio of original to final minimum feature size. For an n-vertex input, we give a triangulation (meshing) algorithm that limits degradation to only a constant factor, as long as Steiner points are allowed on the sides of triangles. If such Steiner points are not allowed, our algorithm realizes degradation. This addresses a 14-year-old open problem by Bern, Dobkin, and Eppstein.

Additional Metadata
Persistent URL
Aloupis, G, Demaine, E.D. (Erik D.), Demaine, M.L. (Martin L.), Dujmović, V, & Iacono, J. (John). (2012). Meshes preserving minimum feature size. doi:10.1007/978-3-642-34191-5_25