On the expected diameter, width, and complexity of a stochastic convex hull

DOI10.1016/j.comgeo.2019.04.002zbMath1468.68272arXiv1704.07028OpenAlexW2936848123WikidataQ127953150 ScholiaQ127953150MaRDI QIDQ2331212

Ravi Janardan, Jie Xue, Yu'an Li

Publication date: 25 October 2019

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1704.07028

zbMATH Keywords

approximation algorithmwidthdiameterconvex hulluncertain datacombinatorial complexityexpectation

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

On the separability of stochastic geometric objects, with applications, QuickhullDisk: a faster convex hull algorithm for disks, A fully polynomial time approximation scheme for the smallest diameter of imprecise points, Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model

Cites Work

• Unnamed Item
• Unnamed Item
• Closest pair and the post office problem for stochastic points
• Largest and smallest convex hulls for imprecise points
• Approximating the diameter of a set of points in the Euclidean space
• Expected computations on color spanning sets
• Stochastic closest-pair problem and most-likely nearest-neighbor search in tree spaces
• Convex hulls under uncertainty
• Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions
• On the Most Likely Convex Hull of Uncertain Points
• On the Most Likely Voronoi Diagramand Nearest Neighbor Searching
• Hyperplane separability and convexity of probabilistic point sets
• Range searching on uncertain data
• Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
• Geometric Computations on Indecisive Points
• Stochastic minimum spanning trees in euclidean spaces