Moment inequalities for random variables in computational geometry

DOI10.1007/BF02280782MaRDI QIDQ1172863zbMATH OpenOpenAlexFDO

Authors Luc 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 algorithmscomputational geometryconvex hullmoment inequalitiesdivide and conqueraverage complexitymaximal vector

Mathematics Subject Classification ID

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

Cites work

• A note on finding convex hulls via maximal vectors
• An efficient algorithm for determining the convex hull of a finite planar set
• 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
• Minimum Covering Ellipses
• On the Distribution of the Number of Admissible Points in a Vector Random Sample
• On the identification of the convex hull of a finite set of points in the plane
• Sur L'enveloppe convexe des nuages de points aleatoires dans Rⁿ. I
• The Minimum Covering Sphere Problem
• The minimum sphere covering a convex polyhedron
• ZufÄllige konvexe Polygone in einem Ringgebiet
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten. II

Cited in

(16)

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

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

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