Peeling meshed potatoes

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

    Research output: Contribution to journalArticle

    Abstract

    We study variants of the potato peeling problem on meshed (triangulated) polygons. Given a polygon with holes, and a triangular mesh that covers its interior (possibly using additional vertices), we want to find a largest-area connected set of triangles of the mesh that is convex, or has some other shape-related property. In particular, we consider (i) convexity, (ii) monotonicity, (iii) bounded backturn, and (iv) bounded total turning angle. The first three problems are solved in polynomial time, whereas the fourth problem is shown to be NP-hard.

    Original languageEnglish (US)
    Pages (from-to)349-367
    Number of pages19
    JournalAlgorithmica (New York)
    Volume60
    Issue number2
    DOIs
    StatePublished - Jun 2011

    Keywords

    • Dynamic programming
    • Geometric optimization
    • Potato peeling

    ASJC Scopus subject areas

    • Computer Science(all)
    • Computer Science Applications
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Peeling meshed potatoes'. Together they form a unique fingerprint.

    Cite this