A polynomial solution for the Potato-peeling problem (Q1076347)

The potato-peeling problem is to find a largest convex set inscribed in a given simple polygon P. The authors consider first the case where the ''potato'' is measured according to area. It was shown in 1981 by Goodman that any optimal solution is polygonal - the intersetion of P and halfplanes defined by chords, maximal segments in P through some of the concave vertices of P. As key notion balanced chains of chords are introduced and several properties derived. Finally a \(O(n^ 7)\) algorithm, including several dynamic programming aspects, is described. Thereby the minimal area potato-peeling problem is shown to be polynomial, which was unknown. Secondly the methods are adapted to the minimal perimeter potato-peeling problem, yielding a \(O(n^ 6)\) algorithm.