Peeling potatoes near-optimally in near-linear time

DOI10.1137/16M1079695MaRDI QIDQ5363383zbMATH OpenOpenAlexFDO

Authors S. Cabello, Josef Cibulka, Jan Kynčl, Maria Saumell, Pavel Valtr

Publication date 6 October 2017

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/16m1079695

zbMATH Keywords

approximation algorithmgeometric optimizationgeometric probabilityvisibility graphpotato peeling

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Randomized algorithms (68W20) Nonnumerical algorithms (68W05) Approximation algorithms (68W25) Convex sets in (2) dimensions (including convex curves) (52A10) Random convex sets and integral geometry (aspects of convex geometry) (52A22)

Recommendations

• Peeling potatoes near-optimally in near-linear time
• Finding largest rectangles in convex polygons
• A polynomial solution for the Potato-peeling problem
• Largest inscribed rectangles in convex polygons
• scientific article; zbMATH DE number 177850

Cites work

• scientific article; zbMATH DE number 1629819 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• A polynomial solution for the Potato-peeling problem
• An algorithm for generalized point location and its applications
• Applications of Parametric Searching in Geometric Optimization
• Approximation of convex bodies by random polytopes
• Approximation of convex figures by pairs of rectangles
• Computational geometry. Algorithms and applications.
• Computing optimal islands
• Computing the visibility graph of points within a polygon
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Convex bodies, economic cap coverings, random polytopes
• Efficient randomized algorithms for some geometric optimization problems
• Finding a guard that sees most and a shop that sells most
• Finding large sticks and potatoes in polygons
• Finding the largest area axis-parallel rectangle in a polygon
• Minimum convex partitions and maximum empty polytopes
• On the Beer index of convexity and its variants
• On the largest convex polygon contained in a non-convex n-gon, or how to peel a potato
• On the mean value of the volume of a random polytope in a convex set
• Peeling meshed potatoes
• Peeling potatoes near-optimally in near-linear time
• Random points and lattice points in convex bodies
• Random polytopes in a convex body
• Ray shooting in polygons using geodesic triangulations
• Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)
• Sequential and parallel algorithms for finding a maximum convex polygon
• Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions
• Stochastic and Integral Geometry
• The convex hull of a random set of points
• The power of geometric duality
• The power of geometric duality revisited
• Triangulating a simple polygon in linear time
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten. II

Cited in

(10)

• Peeling meshed potatoes
• Finding a largest-area triangle in a terrain in near-linear time
• Finding a largest-area triangle in a terrain in near-linear time
• Finding largest rectangles in convex polygons
• Peeling potatoes near-optimally in near-linear time
• A polynomial solution for the Potato-peeling problem
• Large \(k\)-gons in a 1.5D terrain
• Largest triangle inside a terrain
• Peeling potatoes near-optimally in near-linear time
• On the Beer index of convexity and its variants

This page was built for publication: Peeling potatoes near-optimally in near-linear time

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