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 geometrypolynomiallargest 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) Convex sets in (2) dimensions (including convex curves) (52A10) Inequalities and extremum problems involving convexity in convex geometry (52A40) Mathematical programming (90C99)

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

• scientific article; zbMATH DE number 3883624 (Why is no real title available?)
• 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
• 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

(22)

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