Computing the Expected Value and Variance of Geometric Measures
From MaRDI portal
Abstract: Let P be a set of points in R^d, and let M be a function that maps any subset of P to a positive real number. We examine the problem of computing the exact mean and variance of M when a subset of points in P is selected according to a well-defined random distribution. We consider two distributions; in the first distribution (which we call the Bernoulli distribution), each point p in P is included in the random subset independently, with probability pi(p). In the second distribution (the fixed-size distribution), a subset of exactly s points is selected uniformly at random among all possible subsets of s points in P. This problem is a crucial part of modern ecological analyses; each point in P represents a species in d-dimensional trait space, and the goal is to compute the statistics of a geometric measure on this trait space, when subsets of species are selected under random processes. We present efficient exact algorithms for computing the mean and variance of several geometric measures when point sets are selected under one of the described random distributions. More specifically, we provide algorithms for the following measures: the bounding box volume, the convex hull volume, the mean pairwise distance (MPD), the squared Euclidean distance from the centroid, and the diameter of the minimum enclosing disk. We also describe an efficient (1-e)-approximation algorithm for computing the mean and variance of the mean pairwise distance. We implemented three of our algorithms and we show that our implementations can provide major speedups compared to the existing imprecise approaches.
Recommendations
- Computing the Expected Value and Variance of Geometric Measures
- Computation of the mean value and variance functions in geometric process
- On some methods of deriving geometric expectation
- Geometrical bounds for variance and recentered moments
- Calculation of geometric probabilities using covariogram of convex bodies
- A geometrical approach to maximizing a variance
- scientific article; zbMATH DE number 3318582
- Geometric Mean of Nonnegative Random Variable
Cites work
- -kernel coresets for stochastic points
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- An analytical expression and an algorithm for the volume of a convex polyhedron in \(R^ n\).
- An efficient algorithm for determining the convex hull of a finite planar set
- Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
- Expected computations on color spanning sets
- Geometric Computations on Indecisive Points
- scientific article; zbMATH DE number 1538124 (Why is no real title available?)
- Hyperplane separability and convexity of probabilistic point sets
- Largest and smallest convex hulls for imprecise points
- On Approximating the Average Distance Between Points
- On the Most Likely Convex Hull of Uncertain Points
- Probability Inequalities for Sums of Bounded Random Variables
- Shape Fitting on Point Sets with Probability Distributions
Cited in
(4)
This page was built for publication: Computing the Expected Value and Variance of Geometric Measures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4555539)
