A note on the expected time required to construct the outer layer

DOI10.1016/0020-0190(85)90028-6zbMath0572.68032OpenAlexW2009217133MaRDI QIDQ1062448

Luc P. Devroye

Publication date: 1985

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(85)90028-6

zbMATH Keywords

independent random vectorsdivide-and-conquer algorithmouter layer of a set of points

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Records, the maximal layer, and uniform distributions in monotone sets ⋮ On random cartesian trees

Cites Work

• Moment inequalities for random variables in computational geometry
• Divide and conquer for linear expected time
• An efficient algorithm for determining the convex hull of a finite planar set
• Convex hulls of finite sets of points in two and three dimensions
• On the Average Number of Maxima in a Set of Vectors and Applications

This page was built for publication: A note on the expected time required to construct the outer layer