Journal Article

Area and Perimeter of the Convex Hull of Stochastic Points

Pablo Pérez-Lantero

in The Computer Journal

Volume 59, issue 8, pages 1144-1154
Published in print August 2016 | ISSN: 0010-4620
Published online August 2016 | e-ISSN: 1460-2067 | DOI: https://dx.doi.org/10.1093/comjnl/bxv124
Area and Perimeter of the Convex Hull of Stochastic Points

Show Summary Details

Preview

Given a set [math] of [math] 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 [math] of [math] . The random subset [math] is formed by drawing each point [math] of [math] independently with a given rational probability [math] . 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 [math] . For [math] , we provide an algorithm that runs in [math] time and returns a value that is between the probability that the area is at least [math] , and the probability that the area is at least [math] . For the perimeter, we show a similar algorithm running in [math] time. Finally, given [math] and for any measure, we show an [math] -time Monte Carlo algorithm that returns a value that, with probability of success at least [math] , differs at most [math] from the probability that the measure is at least [math] .

Keywords: probabilistic point sets; convex hull; area; perimeter; distribution function; approximation

Journal Article.  7199 words.  Illustrated.

Subjects: Computer Science

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content. subscribe or login to access all content.