Potato Peeling Algorithm
Jump to navigation
Jump to search
A Potato Peeling Algorithm is a Convex Hull Algorithm for finding the largest Convex Polygon within a non-convex polygon.
- AKA: Convex Skull.
- Context:
- It can be implemented by a Potato Peeling System to solve a Potato Peeling Task.
- Example(s):
- Counter-Example(s):
- an Andrew's Monotone Chain Algorithm,
- a Chan's Convex Hull Algorithm,
- a Divide and Conquer Convex Hull Algorithm,
- a Gift Wrapping Algorithm,
- a Graham Scan Algorithm,
- a Kirkpatrick-Seidel Convex Hull Algorithm.
- an Incremental Convex Hull Algorithm,
- a Quickhull Algorithm,
- a ROC Convex Hull Algorithm,
- a Simple Polygon Convex Hull Algorithm.
- See: Approximation Algorithm, Computational Geometry, Convex Polygon, Polygon, Geometriae Dedicata, Polynomial Time, Discrete And Computational Geometry.
References
2020
- (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Potato_peeling Retrieved:2020-3-29.
- 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].
- ↑ 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.
- ↑ 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 and 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, ACM, New York, pp. 474–483, CiteSeerX 10.1.1.59.6770, doi:10.1145/1109557.1109610, ISBN 978-0898716054, MR 2368844.
1986
- (Chang & Yap, 1986) ⇒ J. S. Chang, and C. K. Yap (1986). "A Polynomial Solution For The Potato-Peeling Problem". In: Discrete & Computational Geometry, 1(2). DOI:10.1007/BF02187692
1981
- (Goodman, 1981) ⇒ (1981). "On the Largest Convex Polygon Contained in a Non-convex n-gon, or How to Peel a Potato". In: Geometriae Dedicata, 11(1). DOI:10.1007/BF00183192.