{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:42Z","timestamp":1740109602426,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,5]],"date-time":"2024-12-05T00:00:00Z","timestamp":1733356800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,5]],"date-time":"2024-12-05T00:00:00Z","timestamp":1733356800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"National Science Foundation","award":["1750780"],"award-info":[{"award-number":["1750780"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,1]]},"DOI":"10.1007\/s00454-024-00705-2","type":"journal-article","created":{"date-parts":[[2024,12,5]],"date-time":"2024-12-05T15:47:19Z","timestamp":1733413639000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Linear Expected Complexity for Directional and Multiplicative Voronoi Diagrams"],"prefix":"10.1007","volume":"73","author":[{"given":"Chenglin","family":"Fan","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6584-4843","authenticated-orcid":false,"given":"Benjamin","family":"Raichel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,12,5]]},"reference":[{"issue":"3","key":"705_CR1","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/s00454-014-9626-1","volume":"52","author":"PK Agarwal","year":"2014","unstructured":"Agarwal, P.K., Har-Peled, S., Kaplan, H., et al.: Union of random Minkowski sums and network vulnerability analysis. Discrete Comput. Geom. 52(3), 551\u2013582 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"705_CR2","doi-asserted-by":"crossref","unstructured":"Aronov, B., de\u00a0Berg, M., Thite, S.: The complexity of bisectors and Voronoi diagrams on realistic terrains. In: 16th Annual European Symposium on Algorithms (ESA), pp. 100\u2013111 (2008)","DOI":"10.1007\/978-3-540-87744-8_9"},{"issue":"1","key":"705_CR3","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1137\/0216006","volume":"16","author":"F Aurenhammer","year":"1987","unstructured":"Aurenhammer, F.: Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16(1), 78\u201396 (1987). https:\/\/doi.org\/10.1137\/0216006","journal-title":"SIAM J. Comput."},{"issue":"2","key":"705_CR4","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0031-3203(84)90064-5","volume":"17","author":"F Aurenhammer","year":"1984","unstructured":"Aurenhammer, F., Edelsbrunner, H.: An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recogn. 17(2), 251\u2013257 (1984)","journal-title":"Pattern Recogn."},{"key":"705_CR5","doi-asserted-by":"publisher","DOI":"10.1142\/8685","volume-title":"Voronoi Diagrams and Delaunay Triangulations","author":"F Aurenhammer","year":"2013","unstructured":"Aurenhammer, F., Klein, R., Lee, D.: Voronoi Diagrams and Delaunay Triangulations. World Scientific, Singapore (2013)"},{"key":"705_CR6","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/j.dam.2014.04.009","volume":"174","author":"F Aurenhammer","year":"2014","unstructured":"Aurenhammer, F., Su, B., Xu, Y., et al.: A note on visibility-constrained Voronoi diagrams. Discret. Appl. Math. 174, 52\u201356 (2014)","journal-title":"Discret. Appl. Math."},{"key":"705_CR7","unstructured":"Bienkowski, M., Damerow, V., Meyer auf der Heide, F., et al.: Average case complexity of Voronoi diagrams of n sites from the unit cube. In: (Informal) Proceedings of the 21st European Workshop on Computational Geometry (EuroCG), pp. 167\u2013170 (2005)"},{"key":"705_CR8","doi-asserted-by":"publisher","unstructured":"Bl\u00e4sius, T., Friedrich, T., G\u00f6bel, A., et al.: The impact of heterogeneity and geometry on the proof complexity of random satisfiability. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, pp. 42\u201353 (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.4","DOI":"10.1137\/1.9781611976465.4"},{"issue":"4","key":"705_CR9","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1007\/s00454-016-9784-4","volume":"56","author":"TM Chan","year":"2016","unstructured":"Chan, T.M., Tsakalidis, K.: Optimal deterministic algorithms for 2-d and 3-d shallow cuttings. Discrete Comput. Geom. 56(4), 866\u2013881 (2016). https:\/\/doi.org\/10.1007\/s00454-016-9784-4","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"705_CR10","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1007\/s00454-016-9808-0","volume":"56","author":"H Chang","year":"2016","unstructured":"Chang, H., Har-Peled, S., Raichel, B.: From proximity to utility: a Voronoi partition of Pareto optima. Discrete Comput. Geom. 56(3), 631\u2013656 (2016)","journal-title":"Discrete Comput. Geom."},{"key":"705_CR11","doi-asserted-by":"crossref","unstructured":"Cheng, Y., Li, B., Xu, Y.: Semi Voronoi diagrams. In: Computational Geometry, Graphs and Applications - 9th International Conference (CGGA), pp. 19\u201326 (2010)","DOI":"10.1007\/978-3-642-24983-9_3"},{"issue":"3","key":"705_CR12","doi-asserted-by":"publisher","first-page":"37:1","DOI":"10.1145\/2846099","volume":"12","author":"A Driemel","year":"2016","unstructured":"Driemel, A., Har-Peled, S., Raichel, B.: On the expected complexity of Voronoi diagrams on terrains. ACM Trans. Algorithms 12(3), 37:1-37:20 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"705_CR13","doi-asserted-by":"crossref","unstructured":"Dwyer, R.: Higher-dimensional Voronoi diagrams in linear expected time. In: Proceedings of 5th Annual Symposium on Computational Geometry (SOCG), pp. 326\u2013333 (1989)","DOI":"10.1145\/73833.73869"},{"key":"705_CR14","doi-asserted-by":"publisher","unstructured":"Fan, C., Raichel, B.: Linear expected complexity for directional and multiplicative Voronoi diagrams. In: 28th Annual European Symposium on Algorithms (ESA), pp. 45:1\u201345:18 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.45","DOI":"10.4230\/LIPIcs.ESA.2020.45"},{"key":"705_CR15","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.tcs.2013.08.008","volume":"532","author":"C Fan","year":"2014","unstructured":"Fan, C., Luo, J., Wang, W., et al.: Voronoi diagram with visual restriction. Theor. Comput. Sci. 532, 31\u201339 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"705_CR16","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S Fortune","year":"1987","unstructured":"Fortune, S.: A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153\u2013174 (1987). https:\/\/doi.org\/10.1007\/BF01840357","journal-title":"Algorithmica"},{"key":"705_CR17","volume-title":"Handbook of Discrete and Computational Geometry","author":"JE Goodman","year":"2004","unstructured":"Goodman, J.E., O\u2019Rourke, J.: Handbook of Discrete and Computational Geometry, 2nd edn. Chapman and Hall, London (2004)","edition":"2"},{"issue":"3","key":"705_CR18","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1007\/s00454-015-9675-0","volume":"53","author":"S Har-Peled","year":"2015","unstructured":"Har-Peled, S., Raichel, B.: On the complexity of randomly weighted multiplicative Voronoi diagrams. Discrete Comput. Geom. 53(3), 547\u2013568 (2015)","journal-title":"Discrete Comput. Geom."},{"key":"705_CR19","doi-asserted-by":"publisher","unstructured":"Har-Peled, S., Kaplan, H., Sharir, M.: Approximating the k-level in three-dimensional plane arrangements. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1193\u20131212 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch83","DOI":"10.1137\/1.9781611974331.ch83"},{"key":"705_CR20","doi-asserted-by":"publisher","unstructured":"Lee, D.T., Drysdale III, R.L.: Generalization of Voronoi diagrams in the plane. SIAM J. Comput. 10(1), 73\u201387 (1981). https:\/\/doi.org\/10.1137\/0210006","DOI":"10.1137\/0210006"},{"issue":"2","key":"705_CR21","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1137\/0214034","volume":"14","author":"M Sharir","year":"1985","unstructured":"Sharir, M.: Intersection and closest-pair problems for a set of planar discs. SIAM J. Comput. 14(2), 448\u2013468 (1985). https:\/\/doi.org\/10.1137\/0214034","journal-title":"SIAM J. Comput."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00705-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00705-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00705-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T16:04:55Z","timestamp":1736179495000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00705-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,5]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["705"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00705-2","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2024,12,5]]},"assertion":[{"value":"8 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 October 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 December 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The authors approve and acknowledge our ethical responsibilities.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}},{"value":"The authors give consent for publication.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Informed Consent"}}]}}