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 language | English (US) |
---|---|
Pages (from-to) | 349-367 |
Number of pages | 19 |
Journal | Algorithmica (New York) |
Volume | 60 |
Issue number | 2 |
DOIs | |
State | Published - Jun 2011 |
Keywords
- Dynamic programming
- Geometric optimization
- Potato peeling
ASJC Scopus subject areas
- Computer Science(all)
- Computer Science Applications
- Applied Mathematics