A note on linear expected time algorithms for finding convex hulls

DOI10.1007/BF02237955MaRDI QIDQ1142045zbMATH OpenOpenAlexFDO

Authors Godfried Toussaint, Luc 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

algorithmsconvex hullsaverage complexitygeometrical complexity

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3223982 (Why is no real title available?)
• A New Convex Hull Algorithm for Planar Sets
• A fast convex hull algorithm
• A note on finding convex hulls via maximal vectors
• An efficient algorithm for determining the convex hull of a finite planar set
• Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator
• Average time behavior of distributive sorting algorithms
• Die konvexe H�lle von n rotationssymmetrisch verteilten Punkten
• Divide and conquer for linear expected time
• How to reduce the average complexity of convex hull finding algorithms
• On the Average Number of Maxima in a Set of Vectors and Applications
• On the identification of the convex hull of a finite set of points in the plane
• Optimal Expected-Time Algorithms for Closest Point Problems

Cited in

(4)

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

This page was built for publication: A note on linear expected time algorithms for finding convex hulls

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