Peeling Potatoes Near-Optimally in Near-Linear Time
From MaRDI portal
Publication:5363383
DOI10.1137/16M1079695zbMath1376.52009OpenAlexW3103103930MaRDI QIDQ5363383
Sergio Cabello, Pavel Valtr, Josef Cibulka, Maria Saumell, Jan Kynčl
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
Geometric probability and stochastic geometry (60D05) Nonnumerical algorithms (68W05) Convex sets in (2) dimensions (including convex curves) (52A10) Approximation algorithms (68W25) Randomized algorithms (68W20) Random convex sets and integral geometry (aspects of convex geometry) (52A22)
Related Items
Finding a largest-area triangle in a terrain in near-linear time ⋮ Peeling Potatoes Near-Optimally in Near-Linear Time ⋮ Large \(k\)-gons in a 1.5D terrain ⋮ Largest triangle inside a terrain ⋮ On the Beer index of convexity and its variants
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing optimal islands
- On the Beer index of convexity and its variants
- Peeling meshed potatoes
- Sequential and parallel algorithms for finding a maximum convex polygon
- Finding the largest area axis-parallel rectangle in a polygon
- The power of geometric duality revisited
- A polynomial solution for the Potato-peeling problem
- The power of geometric duality
- Approximation of convex bodies by random polytopes
- On the largest convex polygon contained in a non-convex n-gon, or how to peel a potato
- Triangulating a simple polygon in linear time
- Ray shooting in polygons using geodesic triangulations
- Approximation of convex figures by pairs of rectangles
- Efficient randomized algorithms for some geometric optimization problems
- On the mean value of the volume of a random polytope in a convex set
- Finding a guard that sees most and a shop that sells most
- Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)
- An algorithm for generalized point location and its applications
- Minimum convex partitions and maximum empty polytopes
- Stochastic and Integral Geometry
- Random points and lattice points in convex bodies
- Finding large sticks and potatoes in polygons
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Convex bodies, economic cap coverings, random polytopes
- Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions
- Random polytopes in a convex body
- Applications of Parametric Searching in Geometric Optimization
- [https://portal.mardi4nfdi.de/wiki/Publication:5331598 �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten. II]
- Computing the visibility graph of points within a polygon
- Peeling Potatoes Near-Optimally in Near-Linear Time
- The convex hull of a random set of points
- [https://portal.mardi4nfdi.de/wiki/Publication:5728818 �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten]
