Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Potato peeling
open-in-new
<p>In <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a>, the potato peeling or convex skull problem is a problem of finding the <a href="/facts/Convex_polygon/7x35w610">convex polygon</a> of the largest possible area that lies within a given non-convex <a href="/facts/Simple_polygon/C5CfrPWf">simple polygon</a>. It was posed independently by Goodman and Woo, and solved in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> by Chang and Yap. The exponent of the polynomial time bound is high, but the same problem can also be accurately <a href="/facts/Approximation_algorithm/BWlf7M32">approximated</a> in near-linear time. </p>