Potato peeling
{{about|a problem in computational geometry|the devices used to peel potatoes|peeler}}
In computational geometry, the potato peeling or convex skull problem is a problem of finding the convex polygon of the largest possible area that lies within a given non-convex simple polygon. It was posed independently by Goodman and Woo,{{r|g|w}} and solved in polynomial time by Chang and Yap.{{r|cy}} The exponent of the polynomial time bound is high, but the same problem can also be accurately approximated in near-linear time.{{r|hkkms|ccksv}}
References
{{reflist|refs=
| last1 = Cabello | first1 = Sergio
| last2 = Cibulka | first2 = Josef
| last3 = Kynčl | first3 = Jan
| last4 = Saumell | first4 = Maria
| last5 = Valtr | first5 = Pavel
| doi = 10.1137/16M1079695
| issue = 5
| journal = SIAM Journal on Computing
| mr = 3708542
| pages = 1574–1602
| title = Peeling potatoes near-optimally in near-linear time
| volume = 46
| year = 2017| arxiv = 1406.1368
}}
| last1 = Chang | first1 = J. S.
| last2 = Yap | first2 = C.-K.
| doi = 10.1007/BF02187692
| issue = 2
| journal = Discrete & Computational Geometry
| mr = 834056
| pages = 155–182
| title = A polynomial solution for the potato-peeling problem
| volume = 1
| year = 1986| doi-access = free}}
| last = Goodman | first = Jacob E. | authorlink = Jacob E. Goodman
| doi = 10.1007/BF00183192
| issue = 1
| journal = Geometriae Dedicata
| mr = 608164
| pages = 99–106
| title = On the largest convex polygon contained in a nonconvex {{mvar|n}}-gon, or how to peel a potato
| volume = 11
| year = 1981| s2cid = 121212273 }}
| last1 = Hall-Holt | first1 = Olaf
| last2 = Katz | first2 = Matthew J.
| last3 = Kumar | first3 = Piyush
| last4 = Mitchell | first4 = Joseph S. B. | author4-link = Joseph S. B. Mitchell
| last5 = Sityon | first5 = Arik
| contribution = Finding large sticks and potatoes in polygons
| doi = 10.1145/1109557.1109610
| mr = 2368844
| pages = 474–483
| publisher = ACM | location = New York
| title = Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
| year = 2006| isbn = 978-0898716054
| citeseerx = 10.1.1.59.6770| s2cid = 7212084
}}
}}