Potato peeling
From HandWiki
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,[1][2] and solved in polynomial time by Chang and Yap.[3] The exponent of the polynomial time bound is high, but the same problem can also be accurately approximated in near-linear time.[4][5]
References
- ↑ "On the largest convex polygon contained in a nonconvex n-gon, or how to peel a potato", Geometriae Dedicata 11 (1): 99–106, 1981, doi:10.1007/BF00183192
- ↑ Woo, T. (1983), The convex skull problem, as cited by (Chang Yap)
- ↑ 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
- ↑ Hall-Holt, Olaf; Katz, Matthew J.; Kumar, Piyush (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, doi:10.1145/1109557.1109610, ISBN 978-0898716054
- ↑ 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, doi:10.1137/16M1079695
 |  |
