Convex hulls under uncertainty

DOI10.1007/s00453-016-0195-yzbMath1372.68244arXiv1406.6599OpenAlexW1847264820MaRDI QIDQ2408916

Sariel Har-Peled, Wuzhou Zhang, Subhash Suri, Hakan Yildiz, Pankaj K. Agarwal

Publication date: 10 October 2017

Published in: Algorithmica, Algorithms - ESA 2014 (Search for Journal in Brave)

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

zbMATH Keywords

uncertaintyconvex hullTukey depthmembership probability

Mathematics Subject Classification ID

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

Related Items (22)

On the separability of stochastic geometric objects, with applications ⋮ Separability of imprecise points ⋮ On the arrangement of stochastic lines in \(\mathbb{R}^2\) ⋮ Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points ⋮ Computing the Center of Uncertain Points on Tree Networks ⋮ Computing the Expected Value and Variance of Geometric Measures ⋮ Computing the Rectilinear Center of Uncertain Points in the Plane ⋮ Voronoi Diagram and Delaunay Triangulation with Independent and Dependent Geometric Uncertainties ⋮ r-Gatherings on a star and uncertain r-gatherings on a line ⋮ Half-plane point retrieval queries with independent and dependent geometric uncertainties ⋮ The Most Likely Object to be Seen Through a Window ⋮ Largest and smallest area triangles on imprecise points ⋮ Euclidean minimum spanning trees with independent and dependent geometric uncertainties ⋮ Computing the center of uncertain points on tree networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A fully polynomial time approximation scheme for the smallest diameter of imprecise points ⋮ Covering uncertain points in a tree ⋮ The most-likely skyline problem for stochastic points ⋮ Cardinality estimation for random stopping sets based on Poisson point processes ⋮ On the expected diameter, width, and complexity of a stochastic convex hull ⋮ Computing Shapley values in the plane

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• (Approximate) uncertain skylines
• Closest pair and the post office problem for stochastic points
• Approximating largest convex hulls for imprecise points
• The power of geometric duality
• \(\epsilon\)-nets and simplex range queries
• Cutting hyperplanes for divide-and-conquer
• Largest bounding box, smallest diameter, and related problems on imprecise points
• Constructing strongly convex approximate hulls with inaccurate primitives
• Nearest-neighbor searching under uncertainty. I
• On the Most Likely Convex Hull of Uncertain Points
• Range searching on uncertain data
• Approximate Proximity Drawings
• Approximation algorithms for spreading points
• Delaunay triangulations of imprecise pointsin linear time after preprocessing
• A CONVEX HULL ALGORITHM FOR POINTS WITH APPROXIMATELY KNOWN POSITIONS
• Linear Optimization Queries
• Nearest-Neighbor Searching Under Uncertainty II
• Algorithms for center and Tverberg points
• Geometric Computations on Indecisive Points
• Stochastic minimum spanning trees in euclidean spaces

This page was built for publication: Convex hulls under uncertainty