TY - JOUR
T1 - On the expected diameter, width, and complexity of a stochastic convex hull
AU - Xue, Jie
AU - Li, Yuan
AU - Janardan, Ravi
N1 - Publisher Copyright:
© 2019 Elsevier B.V.
PY - 2019/9
Y1 - 2019/9
N2 - We investigate several computational problems related to the stochastic convex hull (SCH). Given a stochastic dataset consisting of n points in R d each of which has an existence probability, a SCH refers to the convex hull of a realization of the dataset, i.e., a random sample including each point with its existence probability. We are interested in computing certain expected statistics of a SCH, including diameter, width, and combinatorial complexity. For diameter, we establish a deterministic 1.633-approximation algorithm with a time complexity polynomial in both n and d. For width, two approximation algorithms are provided: a deterministic O(1)-approximation running in O(n d+1 logn) time, and a fully polynomial-time randomized approximation scheme (FPRAS). For combinatorial complexity, we propose an exact O(n d )-time algorithm. Our solutions exploit many geometric insights in Euclidean space, some of which might be of independent interest.
AB - We investigate several computational problems related to the stochastic convex hull (SCH). Given a stochastic dataset consisting of n points in R d each of which has an existence probability, a SCH refers to the convex hull of a realization of the dataset, i.e., a random sample including each point with its existence probability. We are interested in computing certain expected statistics of a SCH, including diameter, width, and combinatorial complexity. For diameter, we establish a deterministic 1.633-approximation algorithm with a time complexity polynomial in both n and d. For width, two approximation algorithms are provided: a deterministic O(1)-approximation running in O(n d+1 logn) time, and a fully polynomial-time randomized approximation scheme (FPRAS). For combinatorial complexity, we propose an exact O(n d )-time algorithm. Our solutions exploit many geometric insights in Euclidean space, some of which might be of independent interest.
KW - Approximation algorithm
KW - Convex hull
KW - Expectation
KW - Uncertain data
UR - http://www.scopus.com/inward/record.url?scp=85065023751&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85065023751&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2019.04.002
DO - 10.1016/j.comgeo.2019.04.002
M3 - Article
AN - SCOPUS:85065023751
SN - 0925-7721
VL - 82
SP - 16
EP - 31
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
ER -