Peeling meshed potatoes

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

    Research output: Contribution to journalArticlepeer-review


    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)
    Issue number2
    StatePublished - Jun 2011


    • Dynamic programming
    • Geometric optimization
    • Potato peeling

    ASJC Scopus subject areas

    • General Computer Science
    • Computer Science Applications
    • Applied Mathematics


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

    Cite this