Paper by Erik D. Demaine
- 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.
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.
- This paper is also available from SpringerLink.
- 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.
These pages are generated automagically from a
Last updated July 7, 2020 by