{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:27:48Z","timestamp":1760441268746},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T00:00:00Z","timestamp":1427846400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s00454-015-9675-0","type":"journal-article","created":{"date-parts":[[2015,4,11]],"date-time":"2015-04-11T00:40:26Z","timestamp":1428712826000},"page":"547-568","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On the Complexity of Randomly Weighted Multiplicative Voronoi Diagrams"],"prefix":"10.1007","volume":"53","author":[{"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Raichel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,11]]},"reference":[{"key":"9675_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Har-Peled, S., Kaplan, H., Sharir, M.: Union of random Minkowski sums and network vulnerability analysis. Discrete Comput. Geom. 54, 551\u2013582 (2014). doi: 10.1007\/s00454-014-9626-1","DOI":"10.1007\/s00454-014-9626-1"},{"key":"9675_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Kaplan, H., Sharir, M.: Union of random Minkowski sums and network vulnerability analysis. In: Proceedings of 29th Annual Symposium on Computational Geometry (SoCG), pp. 177\u2013186 (2013)","DOI":"10.1145\/2462356.2462398"},{"issue":"1","key":"9675_CR3","doi-asserted-by":"crossref","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)","journal-title":"SIAM J. Comput."},{"key":"9675_CR4","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F Aurenhammer","year":"1991","unstructured":"Aurenhammer, F.: Voronoi diagrams: a survey of a fundamental geometric data structure. ACM Comput. Surv. 23, 345\u2013405 (1991)","journal-title":"ACM Comput. Surv."},{"issue":"2","key":"9675_CR5","doi-asserted-by":"crossref","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 Recognition 17(2), 251\u2013257 (1984)","journal-title":"Pattern Recognition"},{"key":"9675_CR6","doi-asserted-by":"crossref","DOI":"10.1142\/8685","volume-title":"Voronoi Diagrams and Delaunay Triangulations","author":"F Aurenhammer","year":"2013","unstructured":"Aurenhammer, F., Klein, R., Lee, D.T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific, Singapore (2013)"},{"key":"9675_CR7","unstructured":"Chang, H.C., Har-Peled, S., Raichel, B.: From proximity to utility: A Voronoi partition of Pareto optima. arXiv:1404.3403 (2014)"},{"key":"9675_CR8","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387\u2013421 (1989)","DOI":"10.1007\/BF02187740"},{"key":"9675_CR9","doi-asserted-by":"crossref","unstructured":"Driemel, A., Har-Peled, S., Raichel, B.: On the expected complexity of Voronoi diagrams on terrains. In: Proceedings of 28th Annual Symposium on Computational Geometry (SoCG), pp. 101\u2013110 (2012)","DOI":"10.1145\/2261250.2261266"},{"key":"9675_CR10","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":"9675_CR11","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0925-7721(97)00031-X","volume":"10","author":"S Har-Peled","year":"1998","unstructured":"Har-Peled, S.: An output sensitive algorithm for discrete convex hulls. Comput. Geom. Theory Appl. 10, 125\u2013138 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9675_CR12","doi-asserted-by":"crossref","DOI":"10.1090\/surv\/173","volume-title":"Geometric Approximation Algorithms, Mathematical Surveys and Monographs","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms, Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Providence, RI (2011)"},{"key":"9675_CR13","unstructured":"Har-Peled, S.: On the expected complexity of random convex hulls. CoRR abs\/1111.5340 (2011)"},{"key":"9675_CR14","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Raichel, B.: On the complexity of randomly weighted Voronoi diagrams. In: Proceedings of 30th Annual Symposium on Computational Geometry (SoCG), pp. 232\u2013241 (2014)","DOI":"10.1145\/2582112.2582158"},{"issue":"3","key":"9675_CR15","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/s00454-010-9324-6","volume":"45","author":"H Kaplan","year":"2011","unstructured":"Kaplan, H., Ramos, E., Sharir, M.: The overlay of minimization diagrams in a randomized incremental construction. Discrete Comput. Geom. 45(3), 371\u2013382 (2011)","journal-title":"Discrete Comput. Geom."},{"key":"9675_CR16","doi-asserted-by":"crossref","unstructured":"Klein, R.: Abstract Voronoi diagrams and their applications. In: Workshop on Computational Geometry, pp. 148\u2013157 (1988)","DOI":"10.1007\/3-540-50335-8_31"},{"issue":"9","key":"9675_CR17","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1016\/j.comgeo.2009.03.002","volume":"42","author":"R Klein","year":"2009","unstructured":"Klein, R., Langetepe, E., Nilforoushan, Z.: Abstract Voronoi diagrams revisited. Comput. Geom. 42(9), 885\u2013902 (2009)","journal-title":"Comput. Geom."},{"key":"9675_CR18","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K Mulmuley","year":"1994","unstructured":"Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs (1994)"},{"key":"9675_CR19","doi-asserted-by":"crossref","unstructured":"Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd edn. Probability and Statistics. Wiley, New York (2000)","DOI":"10.1002\/9780470317013"},{"key":"9675_CR20","doi-asserted-by":"crossref","unstructured":"Pettie, S.: Sharp bounds on Davenport\u2013Schinzel sequences of every order. In: Proceedings of 29th Annual Symposium on Computational Geometry (SoCG), SoCG \u201913, pp. 319\u2013328 (2013). doi: 10.1145\/2462356.2462390","DOI":"10.1145\/2462356.2462390"},{"key":"9675_CR21","doi-asserted-by":"crossref","first-page":"35","DOI":"10.2307\/3212146","volume":"7","author":"H Raynaud","year":"1970","unstructured":"Raynaud, H.: Sur l\u2019enveloppe convex des nuages de points aleatoires dans $$R^{n}$$ R n . J. Appl. Probab. 7, 35\u201348 (1970)","journal-title":"J. Appl. Probab."},{"key":"9675_CR22","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF00535300","volume":"2","author":"A R\u00e9nyi","year":"1963","unstructured":"R\u00e9nyi, A., Sulanke, R.: \u00dcber die konvexe H\u00fclle von $$n$$ n zuf\u00e4llig gerw\u00e4hten Punkten I. Z. Wahrsch. Verw. Gebiete 2, 75\u201384 (1963)","journal-title":"Z. Wahrsch. Verw. Gebiete"},{"key":"9675_CR23","volume-title":"Introduction to Integral Geometry","author":"L Santalo","year":"1953","unstructured":"Santalo, L.: Introduction to Integral Geometry. Hermann, Paris (1953)"},{"key":"9675_CR24","doi-asserted-by":"crossref","unstructured":"Schneider, R., Wieacker, J.A.: Integral geometry. In: P.M. Gruber, J.M. Wills (eds.) Handbook of Convex Geometry, vol. B, chap. 5.1, pp. 1349\u20131390. North-Holland, Amsterdam (1993)","DOI":"10.1016\/B978-0-444-89597-4.50022-6"},{"key":"9675_CR25","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/BF02574384","volume":"12","author":"M Sharir","year":"1994","unstructured":"Sharir, M.: Almost tight upper bounds for lower envelopes in higher dimensions. Discrete Comput. Geom. 12, 327\u2013345 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"9675_CR26","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)"},{"key":"9675_CR27","doi-asserted-by":"crossref","unstructured":"Weil, W., Wieacker, J.A.: Stochastic geometry. In: P.M. Gruber, J.M. Wills (eds.) Handbook of Convex Geometry, vol. B, chap. 5.2, pp. 1393\u20131438. North-Holland, Amsterdam (1993)","DOI":"10.1016\/B978-0-444-89597-4.50023-8"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9675-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-015-9675-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9675-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,23]],"date-time":"2019-08-23T07:58:50Z","timestamp":1566547130000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-015-9675-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["9675"],"URL":"https:\/\/doi.org\/10.1007\/s00454-015-9675-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4]]}}}