Largest subsets of triangles in a triangulation

Boris Aronov, Marc Van Kreveld, Maarten Löffler, Rodrigo I. Silveira

    Research output: Contribution to conferencePaper

    Abstract

    Given a triangulation of n points, with some triangles marked "good", this paper discusses the problems of computing the largest-area connected set of good triangles that (i) is convex, (ii) is monotone, (iii) has a bounded total angular change, or (iv) has a bounded negative turning angle. The first, second, and fourth problems are solved in polynomial time, the third problem is NP-hard.

    Original languageEnglish (US)
    Pages213-216
    Number of pages4
    StatePublished - 2007
    Event19th Annual Canadian Conference on Computational Geometry, CCCG 2007 - Ottawa, ON, Canada
    Duration: Aug 20 2007Aug 22 2007

    Other

    Other19th Annual Canadian Conference on Computational Geometry, CCCG 2007
    CountryCanada
    CityOttawa, ON
    Period8/20/078/22/07

    ASJC Scopus subject areas

    • Geometry and Topology

    Fingerprint Dive into the research topics of 'Largest subsets of triangles in a triangulation'. Together they form a unique fingerprint.

  • Cite this

    Aronov, B., Van Kreveld, M., Löffler, M., & Silveira, R. I. (2007). Largest subsets of triangles in a triangulation. 213-216. Paper presented at 19th Annual Canadian Conference on Computational Geometry, CCCG 2007, Ottawa, ON, Canada.