Meshes preserving minimum feature size

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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 languageEnglish (US)
    Title of host publicationComputational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers
    Number of pages16
    StatePublished - 2012
    Event14th Spanish Meeting on Computational Geometry - Alcala de Henares, Spain
    Duration: Jun 27 2011Jun 30 2011

    Publication series

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


    Other14th Spanish Meeting on Computational Geometry
    CityAlcala de Henares

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Meshes preserving minimum feature size'. Together they form a unique fingerprint.

    Cite this