A note on linear expected time algorithms for finding convex hulls

DOI10.1007/BF02237955zbMath0438.68029OpenAlexW1599239418MaRDI QIDQ1142045

Godfried T. Toussaint, Luc P. Devroye

Publication date: 1981

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02237955

zbMATH Keywords

algorithmsaverage complexityconvex hullsgeometrical complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99)

Related Items

Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points ⋮ A note on finding convex hulls via maximal vectors ⋮ On the computer generation of random convex hulls ⋮ Convex-hull algorithms: implementation, testing, and experimentation

Cites Work

• A note on finding convex hulls via maximal vectors
• Average time behavior of distributive sorting algorithms
• How to reduce the average complexity of convex hull finding algorithms
• A fast convex hull algorithm
• Divide and conquer for linear expected time
• An efficient algorithm for determining the convex hull of a finite planar set
• On the identification of the convex hull of a finite set of points in the plane
• Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator
• Optimal Expected-Time Algorithms for Closest Point Problems
• A New Convex Hull Algorithm for Planar Sets
• On the Average Number of Maxima in a Set of Vectors and Applications
• [https://portal.mardi4nfdi.de/wiki/Publication:5588965 Die konvexe H�lle von n rotationssymmetrisch verteilten Punkten]
• Unnamed Item