TY - GEN

T1 - Meshes preserving minimum feature size

AU - Aloupis, Greg

AU - Demaine, Erik D.

AU - Demaine, Martin L.

AU - Dujmović, Vida

AU - Iacono, John

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84869988366&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84869988366&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-34191-5_25

DO - 10.1007/978-3-642-34191-5_25

M3 - Conference contribution

AN - SCOPUS:84869988366

SN - 9783642341908

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 258

EP - 273

BT - Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers

T2 - 14th Spanish Meeting on Computational Geometry

Y2 - 27 June 2011 through 30 June 2011

ER -