Peeling meshed potatoes

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

doi:10.1007/s00453-009-9346-8

Peeling meshed potatoes

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

Research output: Contribution to journal › Article

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	https://doi.org/10.1007/s00453-009-9346-8
State	Published - Jun 2011

Keywords

Dynamic programming
Geometric optimization
Potato peeling

ASJC Scopus subject areas

Computer Science(all)
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/s00453-009-9346-8

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

Cite this

@article{42e2da7b179f47bea050a802447988cd,

title = "Peeling meshed potatoes",

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.",

keywords = "Dynamic programming, Geometric optimization, Potato peeling",

author = "Boris Aronov and {Van Kreveld}, Marc and Maarten L{\"o}ffler and Silveira, {Rodrigo I.}",

year = "2011",

month = jun,

doi = "10.1007/s00453-009-9346-8",

language = "English (US)",

volume = "60",

pages = "349--367",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Peeling meshed potatoes

AU - Aronov, Boris

AU - Van Kreveld, Marc

AU - Löffler, Maarten

AU - Silveira, Rodrigo I.

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

VL - 60

SP - 349

EP - 367

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 2

ER -