Paper by Erik D. Demaine

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)