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, and solved in polynomial time by Chang and Yap. The exponent of the polynomial time bound is high, but the same problem can also be accurately approximated in near-linear time.
References
- Goodman, Jacob E. (1981), "On the largest convex polygon contained in a nonconvex n-gon, or how to peel a potato", Geometriae Dedicata, 11 (1): 99–106, doi:10.1007/BF00183192, MR 0608164, S2CID 121212273
- Woo, T. (1983), The convex skull problem, as cited by Chang & Yap (1986)
- Chang, J. S.; Yap, C.-K. (1986), "A polynomial solution for the potato-peeling problem", Discrete & Computational Geometry, 1 (2): 155–182, doi:10.1007/BF02187692, MR 0834056
- Hall-Holt, Olaf; Katz, Matthew J.; Kumar, Piyush; Mitchell, Joseph S. B.; Sityon, Arik (2006), "Finding large sticks and potatoes in polygons", Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, New York: ACM, pp. 474–483, CiteSeerX 10.1.1.59.6770, doi:10.1145/1109557.1109610, ISBN 978-0898716054, MR 2368844, S2CID 7212084
- Cabello, Sergio; Cibulka, Josef; Kynčl, Jan; Saumell, Maria; Valtr, Pavel (2017), "Peeling potatoes near-optimally in near-linear time", SIAM Journal on Computing, 46 (5): 1574–1602, arXiv:1406.1368, doi:10.1137/16M1079695, MR 3708542