Moment inequalities for random variables in computational geometry

DOI10.1007/BF02280782zbMath0502.60016OpenAlexW37203355MaRDI QIDQ1172863

Luc P. Devroye

Publication date: 1983

Published in: Computing (Search for Journal in Brave)

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

zbMATH Keywords

analysis of algorithmsconvex hullmoment inequalitiescomputational geometryaverage complexitydivide and conquermaximal vector

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Analysis of algorithms and problem complexity (68Q25) Geometric probability and stochastic geometry (60D05)

Related Items (16)

Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points ⋮ How many maxima can there be? ⋮ Records, the maximal layer, and uniform distributions in monotone sets ⋮ Linear programming approaches to the convex hull problem in \(\mathbb{R}^ m\) ⋮ On random cartesian trees ⋮ Intersections with random geometric objects ⋮ An asymptotic theory for recurrence relations based on minimization and maximization. ⋮ Maxima-finding algorithms for multidimensional samples: A two-phase approach ⋮ On the computer generation of random convex hulls ⋮ Convex hulls of samples from spherically symmetric distributions ⋮ Exact asymptotics of divide-and-conquer recurrences ⋮ The excess-mass ellipsiod ⋮ An algorithm for geometric minimum spanning trees requiring nearly linear expected time ⋮ On the variance of the number of maxima in random vectors and its applications ⋮ A note on the expected time required to construct the outer layer ⋮ Maximal and minimal balls

Cites Work

• A note on finding convex hulls via maximal vectors
• How to reduce the average complexity of convex hull finding algorithms
• 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
• Minimum Covering Ellipses
• The minimum sphere covering a convex polyhedron
• On the Distribution of the Number of Admissible Points in a Vector Random Sample
• [https://portal.mardi4nfdi.de/wiki/Publication:5331598 �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten. II]
• ZufÄllige konvexe Polygone in einem Ringgebiet
• Sur L'enveloppe convexe des nuages de points aleatoires dans Rⁿ. I
• [https://portal.mardi4nfdi.de/wiki/Publication:5588965 Die konvexe H�lle von n rotationssymmetrisch verteilten Punkten]
• The Minimum Covering Sphere Problem
• [https://portal.mardi4nfdi.de/wiki/Publication:5728818 �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten]

This page was built for publication: Moment inequalities for random variables in computational geometry