A polynomial solution for the Potato-peeling problem

DOI10.1007/BF02187692zbMath0593.52007OpenAlexW2062138633MaRDI QIDQ1076347

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

algorithmpolynomialcomputational geometrylargest inscribed polygonminimal area potato-peeling problemminimal perimeter

Mathematics Subject Classification ID

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

Related Items (19)

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

Cites Work

• Unnamed Item
• The complexity of elementary algebra and geometry
• On the largest convex polygon contained in a non-convex n-gon, or how to peel a potato
• Finding the smallest triangles containing a given convex polygon
• Finding minimal enclosing boxes
• Circumscribing a convex polygon by a polygon of fewer sides with minimal area addition
• An optimal algorithm for finding minimal enclosing triangles
• On Shortest Paths in Polyhedral Spaces
• Geometric Extremum Problems

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