**Reference**:- Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, and John Iacono, “Meshes preserving minimum feature size”, in
*Revised Papers from the 14th Spanish Meeting on Computational Geometry (EGC 2011)*, edited by Alberto Márquez, Pedro Ramos, and Jorge Urrutia, Lecture Notes in Computer Science, volume 7579, Alcalá de Henares, Spain, June 27–30, 2011, pages 258–273. **Abstract**:-
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*O*(lg*n*) degradation. This addresses a 14-year-old open problem by Bern, Dobkin, and Eppstein. **Comments**:- This paper is also available from SpringerLink.
**Availability**:- The paper is available in PDF (513k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- FeatureSize_EGC2011 (Meshes preserving minimum feature size)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.