Meshes preserving minimum feature size

Greg Aloupis; Erik D. Demaine; Martin L. Demaine; Vida Dujmović; John Iacono

doi:10.1007/978-3-642-34191-5_25

Meshes preserving minimum feature size

Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, John Iacono

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 degradation. This addresses a 14-year-old open problem by Bern, Dobkin, and Eppstein.

Original language	English (US)
Title of host publication	Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers
Pages	258-273
Number of pages	16
DOIs	https://doi.org/10.1007/978-3-642-34191-5_25
State	Published - 2012
Event	14th Spanish Meeting on Computational Geometry - Alcala de Henares, Spain Duration: Jun 27 2011 → Jun 30 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7579 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	14th Spanish Meeting on Computational Geometry
Country/Territory	Spain
City	Alcala de Henares
Period	6/27/11 → 6/30/11

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Aloupis, G., Demaine, E. D., Demaine, M. L., Dujmović, V., & Iacono, J. (2012). Meshes preserving minimum feature size. In Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers (pp. 258-273). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7579 LNCS). https://doi.org/10.1007/978-3-642-34191-5_25

Meshes preserving minimum feature size. / Aloupis, Greg; Demaine, Erik D.; Demaine, Martin L. et al.
Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers. 2012. p. 258-273 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7579 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aloupis, G, Demaine, ED, Demaine, ML, Dujmović, V & Iacono, J 2012, Meshes preserving minimum feature size. in Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7579 LNCS, pp. 258-273, 14th Spanish Meeting on Computational Geometry, Alcala de Henares, Spain, 6/27/11. https://doi.org/10.1007/978-3-642-34191-5_25

Aloupis G, Demaine ED, Demaine ML, Dujmović V, Iacono J. Meshes preserving minimum feature size. In Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers. 2012. p. 258-273. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-34191-5_25

Aloupis, Greg ; Demaine, Erik D. ; Demaine, Martin L. et al. / Meshes preserving minimum feature size. Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers. 2012. pp. 258-273 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{435b460282a84a73bf35284b0ed9eaff,

title = "Meshes preserving minimum feature size",

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 degradation. This addresses a 14-year-old open problem by Bern, Dobkin, and Eppstein.",

author = "Greg Aloupis and Demaine, {Erik D.} and Demaine, {Martin L.} and Vida Dujmovi{\'c} and John Iacono",

year = "2012",

doi = "10.1007/978-3-642-34191-5_25",

language = "English (US)",

isbn = "9783642341908",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "258--273",

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

note = "14th Spanish Meeting on Computational Geometry ; Conference date: 27-06-2011 Through 30-06-2011",

}

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 -

Meshes preserving minimum feature size

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this