A polynomial solution for the Potato-peeling problem

DOI10.1007/BF02187692MaRDI QIDQ1076347zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1986

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/130988

zbMATH Keywords

algorithmcomputational geometrylargest inscribed polygonminimal area potato-peeling problemminimal perimeterpolynomial

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Convex sets in (2) dimensions (including convex curves) (52A10) Inequalities and extremum problems involving convexity in convex geometry (52A40) Analysis of algorithms and problem complexity (68Q25) Mathematical programming (90C99)

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.

Recommendations

• Peeling potatoes near-optimally in near-linear time
• Peeling potatoes near-optimally in near-linear time
• Peeling meshed potatoes
• The orthogonal convex skull problem
• Finding largest rectangles in convex polygons

Cites work

• An optimal algorithm for finding minimal enclosing triangles
• Circumscribing a convex polygon by a polygon of fewer sides with minimal area addition
• Finding minimal enclosing boxes
• Finding the smallest triangles containing a given convex polygon
• Geometric Extremum Problems
• scientific article; zbMATH DE number 3883624 (Why is no real title available?)
• On Shortest Paths in Polyhedral Spaces
• On the largest convex polygon contained in a non-convex n-gon, or how to peel a potato
• The complexity of elementary algebra and geometry

Cited in

(23)

• The orthogonal convex skull problem
• Rotational polygon overlap minimization and compaction
• Finding a largest rectangle inside a digital object and rectangularization
• Largest triangle inside a terrain
• Largest triangles in a polygon
• Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance
• ROC curves in cost space
• Redistricting without gerrymandering, utilizing the convexity ratio, and other applications to business and industry
• Peeling potatoes near-optimally in near-linear time
• OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS
• A Solution of Conway's Fried Potato Problem
• Scandinavian thins on top of cake: new and improved algorithms for stacking and packing
• An Algorithm to Compute Any Simple k-gon of a Maximum Area or Perimeter Inscribed in a Region of Interest
• Peeling meshed potatoes
• Peeling potatoes near-optimally in near-linear time
• Convex Polygons in Geometric Triangulations
• Large \(k\)-gons in a 1.5D terrain
• Largest unit rectangles inscribed in a convex polygon
• Finding the largest area axis-parallel rectangle in a polygon
• Geometric Knapsack problems
• Finding a largest-area triangle in a terrain in near-linear time
• Maximum-area and maximum-perimeter rectangles in polygons
• Finding a largest-area triangle in a terrain in near-linear time

This page was built for publication: A polynomial solution for the Potato-peeling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1076347)