Convex hulls under uncertainty
From MaRDI portal
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
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
- (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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Convex hulls under uncertainty
