TY - JOUR
T1 - Peeling meshed potatoes
AU - Aronov, Boris
AU - Van Kreveld, Marc
AU - Löffler, Maarten
AU - Silveira, Rodrigo I.
N1 - Funding Information:
Work by B.A. has been supported in part by a grant from the U.S.-Israeli Binational Science Foundation and by NSA MSP Grant H98230-06-1-0016. Partially funded by the Netherlands Organization for Scientific Research (NWO) under FOCUS/BRICKS grant number 642.065.503, and under the project GOGO.
PY - 2011/6
Y1 - 2011/6
N2 - 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.
AB - 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.
KW - Dynamic programming
KW - Geometric optimization
KW - Potato peeling
UR - http://www.scopus.com/inward/record.url?scp=79953226698&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79953226698&partnerID=8YFLogxK
U2 - 10.1007/s00453-009-9346-8
DO - 10.1007/s00453-009-9346-8
M3 - Article
AN - SCOPUS:79953226698
SN - 0178-4617
VL - 60
SP - 349
EP - 367
JO - Algorithmica (New York)
JF - Algorithmica (New York)
IS - 2
ER -