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

作     者：Xue, Jie Li, Yuan Janardan, Ravi 

作者机构：Univ Minnesota Twin Cities Dept Comp Sci & Engn Minneapolis MN 55455 USA 

出 版 物：《COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS》 (计算几何学)

年 卷 期：2019年第82卷

页      面：16-31页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Doctoral Dissertation Fellowship from the Graduate School of the University of Minnesota 

主　　题：Convex hull Uncertain data Expectation Approximation algorithm 

摘      要：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) log n) 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. (C) 2019 Elsevier B.V. All rights reserved.