Area and Perimeter of the Convex Hull of Stochastic Points

2014/12/16 by Pablo Pérez-Lantero, Pérez-Lantero, Pablo
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG

paper · pdf · doi:10.48550/arxiv.1412.5153

arxiv created 2015/09/09 · arxiv updated 2015/09/10

Abstract

Given a set P of n points in the plane, we study the computation of the probability distribution function of both the area and perimeter of the convex hull of a random subset S of P. The random subset S is formed by drawing each point p of P independently with a given rational probability π_p. For both measures of the convex hull, we show that it is #P-hard to compute the probability that the measure is at least a given bound w. For ε∈(0,1), we provide an algorithm that runs in O(n⁶/ε) time and returns a value that is between the probability that the area is at least w, and the probability that the area is at least (1-ε)w. For the perimeter, we show a similar algorithm running in O(n⁶/ε) time. Finally, given ε,δ∈(0,1) and for any measure, we show an O(nlog n+ (n/ε²)log(1/δ))-time Monte Carlo algorithm that returns a value that, with probability of success at least 1-δ, differs at most ε from the probability that the measure is at least w.

Related

• On the expected diameter, width, and complexity of a stochastic convex-hull
• The convex hull of random points on the boundary of a simple polytope
• The minimum neighborliness of a random polytope
• Convex Hull for Probabilistic Points
• Large convex holes in random point sets