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