A polynomial solution for the Potato-peeling problem (Q1076347)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A polynomial solution for the Potato-peeling problem |
scientific article |
Statements
A polynomial solution for the Potato-peeling problem (English)
0 references
1986
0 references
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.
0 references
computational geometry
0 references
largest inscribed polygon
0 references
polynomial
0 references
algorithm
0 references
minimal area potato-peeling problem
0 references
minimal perimeter
0 references