A polynomial solution for the Potato-peeling problem
type: Item
instance of: scholarly article
title: A polynomial solution for the Potato-peeling problem
zbMATH Open document ID: 0593.52007
DOI: 10.1007/BF02187692
author: B. George
published in: Discrete \& Computational Geometry
publication date: 1986-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/130988
review text: 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.
Mathematics Subject Classification ID: 52A40
Mathematics Subject Classification ID: 52A10
Mathematics Subject Classification ID: 90C99
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 52-04
zbMATH DE Number: 3953707
zbMATH Keywords: computational geometry
zbMATH Keywords: largest inscribed polygon
zbMATH Keywords: polynomial
zbMATH Keywords: algorithm
zbMATH Keywords: minimal area potato-peeling problem
zbMATH Keywords: minimal perimeter
reviewed by: Frank Plastria
MaRDI profile type: Publication
cites work: The complexity of elementary algebra and geometry
cites work: Geometric Extremum Problems
cites work: Q3217615
cites work: Circumscribing a convex polygon by a polygon of fewer sides with minimal area addition
cites work: On the largest convex polygon contained in a non-convex n-gon, or how to peel a potato
cites work: Finding the smallest triangles containing a given convex polygon
cites work: An optimal algorithm for finding minimal enclosing triangles
cites work: Finding minimal enclosing boxes
cites work: On Shortest Paths in Polyhedral Spaces
OpenAlex ID: W2062138633
description: scientific article; zbMATH DE number 3953707