{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:34:03Z","timestamp":1750221243004,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2018,7,18]],"date-time":"2018-07-18T00:00:00Z","timestamp":1531872000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2018,11,15]]},"abstract":"<jats:p>Let<jats:italic>P<\/jats:italic>be a point set in \u211d<jats:sup>d<\/jats:sup>, and let<jats:italic>M<\/jats:italic>be a function that maps any subset of<jats:italic>P<\/jats:italic>to a positive real. We examine the problem of computing the mean and variance of<jats:italic>M<\/jats:italic>when a subset in<jats:italic>P<\/jats:italic>is selected according to a random distribution. We consider two distributions; in the first distribution (the Bernoulli distribution), each point<jats:italic>p<\/jats:italic>in<jats:italic>P<\/jats:italic>is included in the random subset independently, with probability \u03c0(<jats:italic>p<\/jats:italic>). In the second distribution (the fixed-size distribution), exactly<jats:italic>s<\/jats:italic>points are selected uniformly at random among all possible subsets of<jats:italic>s<\/jats:italic>points in<jats:italic>P<\/jats:italic>.<\/jats:p><jats:p>We present efficient algorithms for computing the mean and variance of several geometric measures when point sets are selected under one of the described random distributions. We also implemented four of those algorithms: an algorithm that computes the mean 2D bounding box volume in the Bernoulli distribution, an algorithm for the mean 2D convex hull area in the fixed-size distribution, an algorithm that computes the exact mean and variance of the mean pairwise distance (MPD) for<jats:italic>d<\/jats:italic>-dimensional point sets in the fixed-size distribution, and an (1 \u2212 \u03b5)-approximation algorithm for the same measure. We conducted experiments where we compared the performance of our implementations with a standard heuristic approach, and we show that our implementations are very efficient. We also compared the implementation of our exact MPD algorithm and the (1 \u2212 \u03b5)-approximation algorithm; the approximation method performs faster on real-world datasets for point sets of up to 13 dimensions, and provides high-precision approximations.<\/jats:p>","DOI":"10.1145\/3228331","type":"journal-article","created":{"date-parts":[[2018,7,16]],"date-time":"2018-07-16T13:25:21Z","timestamp":1531747521000},"page":"1-32","source":"Crossref","is-referenced-by-count":0,"title":["Computing the Expected Value and Variance of Geometric Measures"],"prefix":"10.1145","volume":"23","author":[{"given":"Constantinos","family":"Tsirogiannis","sequence":"first","affiliation":[{"name":"MADALGO, Aarhus University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Staals","sequence":"additional","affiliation":[{"name":"MADALGO, Aarhus University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Pellissier","sequence":"additional","affiliation":[{"name":"Ecoinformatics and Biodiversity, Aarhus University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,7,18]]},"reference":[{"volume-title":"European Symposium on Algorithms. Springer, 37--48","author":"Agarwal P. K.","key":"e_1_2_1_1_1"},{"volume-title":"On Approximating the Average Distance Between Points","author":"Barhum Kfir","key":"e_1_2_1_2_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-74208-1_22"},{"volume-title":"Multi-scale phylogenetic structure in coastal dune plant communities across the globe. Journal of Plant Ecology","year":"2014","author":"Brunbjerg A. K.","key":"e_1_2_1_3_1"},{"volume-title":"Exact","author":"B\u00fceler Benno","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1890\/0012-9658(2006)87[1465:ATTFHF]2.0.CO;2"},{"volume-title":"Proceedings of the 32nd International Symposium on Computational Geometry (SoCG\u201916)","author":"Fink M.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1890\/0012-9658(2000)081[2606:NMAOSC]2.0.CO;2"},{"volume-title":"A general coefficient of similarity and some of its properties. Biometrics","year":"1971","author":"Gower J. C.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(72)90045-2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"volume-title":"Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points","author":"Huang Lingxiao","key":"e_1_2_1_12_1"},{"volume-title":"Workshop on Algorithms and Data Structures. Springer, 536--547","author":"J\u00f8rgensen A.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00934543"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-014-9764-7"},{"key":"e_1_2_1_16_1","unstructured":"L. Huang J. Li J. M. Phillips and H. Wang. 2016. Epsilon-kernel coresets for stochastic points. Retrieved July 7 2018 from https:\/\/arxiv.org\/abs\/1411.0194. L. Huang J. Li J. M. Phillips and H. Wang. 2016. Epsilon-kernel coresets for stochastic points. Retrieved July 7 2018 from https:\/\/arxiv.org\/abs\/1411.0194."},{"volume-title":"Proceedings of the 17th Annual European Symposium on Algorithms (ESA\u201909)","author":"L\u00f6ffler Maarten","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9174-2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1365-2656.2007.01350.x"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1365-2435.2010.01695.x"},{"volume-title":"European Symposium on Algorithms. Springer, 791--802","author":"Suri S.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"1056","DOI":"10.1111\/ecog.00763","article-title":"On the packing and filling of functional space in eastern North American tree assemblages","volume":"37","author":"Swenson N. G.","year":"2014","journal-title":"Ecography"},{"volume-title":"GitHub Repository of Geometric-Measure Statistics Code. Retrieved","year":"2018","author":"Tsirogiannis C.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1890\/07-1206.1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s100219900062"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep12731"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3228331","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3228331","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:34Z","timestamp":1750212454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3228331"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,18]]},"references-count":26,"alternative-id":["10.1145\/3228331"],"URL":"https:\/\/doi.org\/10.1145\/3228331","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2018,7,18]]}}}