Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

**Computing the Expected Value and Variance of Geometric Measures.** / Staals, Frank; Tsirogiannis, Constantinos.

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

Staals, F & Tsirogiannis, C 2017, Computing the Expected Value and Variance of Geometric Measures. in S Fekete & V Ramachandran (eds), *2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX).* Society for Industrial and Applied Mathematics, pp. 232 - 246, ALENEX17, Barcelona, Spain, 17/01/2017. https://doi.org/10.1137/1.9781611974768.19

Staals, F., & Tsirogiannis, C. (2017). Computing the Expected Value and Variance of Geometric Measures. In S. Fekete, & V. Ramachandran (Eds.), *2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX) *(pp. 232 - 246). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611974768.19

Staals F, Tsirogiannis C. 2017. Computing the Expected Value and Variance of Geometric Measures. Fekete S, Ramachandran V, editors. In 2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics. pp. 232 - 246. https://doi.org/10.1137/1.9781611974768.19

Staals, Frank and Constantinos Tsirogiannis "Computing the Expected Value and Variance of Geometric Measures". and Fekete, Sándor Ramachandran , Vijaya (editors). *2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX).* Society for Industrial and Applied Mathematics. 2017, 232 - 246. https://doi.org/10.1137/1.9781611974768.19

Staals F, Tsirogiannis C. Computing the Expected Value and Variance of Geometric Measures. In Fekete S, Ramachandran V, editors, 2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics. 2017. p. 232 - 246 https://doi.org/10.1137/1.9781611974768.19

Staals, Frank ; Tsirogiannis, Constantinos. / **Computing the Expected Value and Variance of Geometric Measures**. 2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX). editor / Sándor Fekete ; Vijaya Ramachandran . Society for Industrial and Applied Mathematics, 2017. pp. 232 - 246

@inproceedings{b6ad9e5f41774cdfafc2fb8a9537c961,

title = "Computing the Expected Value and Variance of Geometric Measures",

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.",

keywords = "cs.DS",

author = "Frank Staals and Constantinos Tsirogiannis",

year = "2017",

doi = "10.1137/1.9781611974768.19",

language = "English",

pages = "232 -- 246",

editor = "Fekete, {S{\'a}ndor } and {Ramachandran }, {Vijaya }",

booktitle = "2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX)",

publisher = "Society for Industrial and Applied Mathematics",

note = "null ; Conference date: 17-01-2017 Through 18-01-2017",

url = "http://epubs.siam.org/doi/book/10.1137/1.9781611974768",

}

TY - GEN

T1 - Computing the Expected Value and Variance of Geometric Measures

AU - Staals, Frank

AU - Tsirogiannis, Constantinos

N1 - Conference code: 19

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - cs.DS

U2 - 10.1137/1.9781611974768.19

DO - 10.1137/1.9781611974768.19

M3 - Article in proceedings

SP - 232

EP - 246

BT - 2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX)

A2 - Fekete, Sándor

A2 - Ramachandran , Vijaya

PB - Society for Industrial and Applied Mathematics

Y2 - 17 January 2017 through 18 January 2017

ER -