Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points
From MaRDI portal
Publication:2365326
DOI10.1007/BF02770866zbMath0876.68052OpenAlexW2002241753MaRDI QIDQ2365326
Publication date: 12 November 1997
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02770866
Geometric probability and stochastic geometry (60D05) Parallel algorithms in computer science (68W10) Random convex sets and integral geometry (aspects of convex geometry) (52A22)
Related Items (1)
Cites Work
- Unnamed Item
- The simplex method. A probabilistic analysis
- A note on linear expected time algorithms for finding convex hulls
- How to reduce the average complexity of convex hull finding algorithms
- Moment inequalities for random variables in computational geometry
- Convex hulls of samples from spherically symmetric distributions
- Small-dimensional linear programming and convex hulls made easy
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- A fast convex hull algorithm
- Divide and conquer for linear expected time
- Applications of random sampling in computational geometry. II
- A randomized algorithm for fixed-dimensional linear programming
- Random convex hulls in a product of balls
- Linear programming in \(O(n\times 3^{d^2})\) time
- An efficient algorithm for determining the convex hull of a finite planar set
- Linear Time Algorithms for Two- and Three-Variable Linear Programs
- Finding the convex hull facet by facet
- Linear Programming in Linear Time When the Dimension Is Fixed
- On the convex hull of random points in a polytope
- A Problem in Geometric Probability.
- The convex hull of a uniform sample from the interior of a simple d-polytope
- An Algorithm for Convex Polytopes
This page was built for publication: Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points
