Potato peeling

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

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]

  1. ^ Cite error: The named reference g was invoked but never defined (see the help page).
  2. ^ Cite error: The named reference w was invoked but never defined (see the help page).
  3. ^ Cite error: The named reference cy was invoked but never defined (see the help page).
  4. ^ Cite error: The named reference hkkms was invoked but never defined (see the help page).
  5. ^ Cite error: The named reference ccksv was invoked but never defined (see the help page).