Peeling Meshed Potatoes

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 convexity, monotonicity, bounded backturn, and bounded total turning angle. The first three problems are solved in polynomial time, whereas the fourth problem is shown to be NP-hard.

slides

Journal Article (peer-reviewed)

Conference Proceedings (peer-reviewed)

Technical Report (not reviewed)

back to list