{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:14:43Z","timestamp":1750306483869,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,4,25]],"date-time":"2016-04-25T00:00:00Z","timestamp":1461542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Netherlands Organisation for Scientific Research","doi-asserted-by":"crossref","award":["612.065.823"],"award-info":[{"award-number":["612.065.823"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF AF","award":["CCF-0915984 and CCF-1217462"],"award-info":[{"award-number":["CCF-0915984 and CCF-1217462"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,6,15]]},"abstract":"<jats:p>\n            We investigate the combinatorial complexity of geodesic Voronoi diagrams on polyhedral terrains using a probabilistic analysis. Aronov et al. [2008] prove that, if one makes certain realistic input assumptions on the terrain, this complexity is \u0398(\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            \u221a\n            <jats:italic>n<\/jats:italic>\n            ) in the worst case, where\n            <jats:italic>n<\/jats:italic>\n            denotes the number of triangles that define the terrain and\n            <jats:italic>m<\/jats:italic>\n            denotes the number of Voronoi sites. We prove that, under a relaxed set of assumptions, the Voronoi diagram has expected complexity\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            ), given that the sites are sampled uniformly at random from the domain of the terrain (or the surface of the terrain). Furthermore, we present a construction of a terrain that implies a lower bound of \u03a9(\n            <jats:italic>nm<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            ) on the expected worst-case complexity if these assumptions on the terrain are dropped. As an additional result, we show that the expected fatness of a cell in a random planar Voronoi diagram is bounded by a constant.\n          <\/jats:p>","DOI":"10.1145\/2846099","type":"journal-article","created":{"date-parts":[[2016,4,25]],"date-time":"2016-04-25T19:51:13Z","timestamp":1461613873000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Expected Complexity of Voronoi Diagrams on Terrains"],"prefix":"10.1145","volume":"12","author":[{"given":"Anne","family":"Driemel","sequence":"first","affiliation":[{"name":"TU Eindhoven, MB Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sariel","family":"Har-Peled","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Raichel","sequence":"additional","affiliation":[{"name":"University of Texas at Dallas, Richardson, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,4,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658810110038942"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0961-x"},{"volume-title":"New Perspectives in Stochastic Geometry","author":"Calka P.","key":"e_1_2_1_4_1","unstructured":"P. Calka . 2010. Tessellations . In New Perspectives in Stochastic Geometry , W. S. Kendall and I. Molchanov (Eds.). Oxford University Press , London, UK , 606. P. Calka. 2010. Tessellations. In New Perspectives in Stochastic Geometry, W. S. Kendall and I. Molchanov (Eds.). Oxford University Press, London, UK, 606."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10310-009-0170-4"},{"key":"e_1_2_1_6_1","first-page":"57","article-title":"Visibility maps of realistic terrains have linear smoothed complexity","volume":"1","author":"de Berg M.","year":"2010","unstructured":"M. de Berg , H. J. Haverkort , and C. P. Tsirogiannis . 2010 . Visibility maps of realistic terrains have linear smoothed complexity . Journal of Computational Geometry 1 , 1, 57 -- 71 . http:\/\/jocg.org\/index.php\/ jocg\/article\/view\/12. M. de Berg, H. J. Haverkort, and C. P. Tsirogiannis. 2010. Visibility maps of realistic terrains have linear smoothed complexity. Journal of Computational Geometry 1, 1, 57--71. http:\/\/jocg.org\/index.php\/ jocg\/article\/view\/12.","journal-title":"Journal of Computational Geometry"},{"volume-title":"Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Devillers O.","key":"e_1_2_1_7_1","unstructured":"O. Devillers , J. Erickson , and X. Goaoc . 2008. Empty-ellipse graphs . In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908) . SIAM, Philadelphia, PA, 1249--1257. http:\/\/dl.acm.org\/citation.cfm?id&equals;1347082.1347218. O. Devillers, J. Erickson, and X. Goaoc. 2008. Empty-ellipse graphs. In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). SIAM, Philadelphia, PA, 1249--1257. http:\/\/dl.acm.org\/citation.cfm?id&equals;1347082.1347218."},{"volume-title":"Curve and Surface Reconstruction: Algorithms with Mathematical Analysis","author":"Dey T. K.","key":"e_1_2_1_8_1","unstructured":"T. K. Dey . 2011. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis . Cambridge University Press , Cambridge, UK . http:\/\/books.google.com\/books?id&equals;HriFSQAACAAJ. T. K. Dey. 2011. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Cambridge University Press, Cambridge, UK. http:\/\/books.google.com\/books?id&equals;HriFSQAACAAJ."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1463434.1463504"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2261250.2261266"},{"key":"e_1_2_1_11_1","unstructured":"F. Jarai-Szabo and Z. Neda. 2004. On the size-distribution of Poisson Voronoi cells. CoRR abs\/cond-mat\/0406116 Article 0406116 12 pages.  F. Jarai-Szabo and Z. Neda. 2004. On the size-distribution of Poisson Voronoi cells. CoRR abs\/cond-mat\/0406116 Article 0406116 12 pages."},{"volume-title":"Proceedings of Comp. Graph. Int. IEEE Computer Society","author":"Kunze R.","key":"e_1_2_1_12_1","unstructured":"R. Kunze , F.-E. Wolter , and T. Rausch . 1997. Geodesic Voronoi diagrams on parametric surfaces . In Proceedings of Comp. Graph. Int. IEEE Computer Society , Washington, DC, USA, 230--237. R. Kunze, F.-E. Wolter, and T. Rausch. 1997. Geodesic Voronoi diagrams on parametric surfaces. In Proceedings of Comp. Graph. Int. IEEE Computer Society, Washington, DC, USA, 230--237."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.10.008"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470317013"},{"key":"e_1_2_1_17_1","volume-title":"Consumer Communications and Networking Conference","volume":"2","author":"Portela J. N.","unstructured":"J. N. Portela and M. S. Alencar . 2006. Cellular network as a multiplicatively weighted Voronoi diagram . In Consumer Communications and Networking Conference , Vol. 2 . IEEE, Washington, DC, 913--917. J. N. Portela and M. S. Alencar. 2006. Cellular network as a multiplicatively weighted Voronoi diagram. In Consumer Communications and Networking Conference, Vol. 2. IEEE, Washington, DC, 913--917."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.2307\/3212146"},{"volume-title":"New Perspectives in Stochastic Geometry","author":"Reitzner M.","key":"e_1_2_1_19_1","unstructured":"M. Reitzner . 2010. Random polytopes . In New Perspectives in Stochastic Geometry , W. S. Kendall and I. Molchanov (Eds.). Oxford University Press , London, UK , 606. M. Reitzner. 2010. Random polytopes. In New Perspectives in Stochastic Geometry, W. S. Kendall and I. Molchanov (Eds.). Oxford University Press, London, UK, 606."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00535300"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1021"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"R. Schneider and W. Weil. 2010. Classical stochastic geometry. In New Perspectives in Stochastic Geometry W. S. Kendall and I. Molchanov (Eds.). Oxford University Press London UK 606.  R. Schneider and W. Weil. 2010. Classical stochastic geometry. In New Perspectives in Stochastic Geometry W. S. Kendall and I. Molchanov (Eds.). Oxford University Press London UK 606.","DOI":"10.1093\/acprof:oso\/9780199232574.003.0001"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247069.1247081"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116660.3117010"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2004.24"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.88035"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409625.1409626"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2846099","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2846099","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:25Z","timestamp":1750225705000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2846099"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,25]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6,15]]}},"alternative-id":["10.1145\/2846099"],"URL":"https:\/\/doi.org\/10.1145\/2846099","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2016,4,25]]},"assertion":[{"value":"2014-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}