Potato peeling

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 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]

This article is about a problem in computational geometry. For the devices used to peel potatoes, see peeler.

References
  1. 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.
  2. Woo, T. (1983), The convex skull problem. As cited by Chang & Yap (1986).
  3. Chang, J. S.; Yap, C.-K. (1986), "A polynomial solution for the potato-peeling problem", Discrete and Computational Geometry, 1 (2): 155–182, doi:10.1007/BF02187692, MR 0834056.
  4. 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, ACM, New York, pp. 474–483, CiteSeerX 10.1.1.59.6770, doi:10.1145/1109557.1109610, ISBN 978-0898716054, MR 2368844.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.