{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T12:36:24Z","timestamp":1765888584796},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T00:00:00Z","timestamp":1617840000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T00:00:00Z","timestamp":1617840000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00454-020-00274-0","type":"journal-article","created":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T14:03:06Z","timestamp":1617890586000},"page":"1136-1165","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Union of Hypercubes and 3D Minkowski Sums with Random Sizes"],"prefix":"10.1007","volume":"65","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,8]]},"reference":[{"issue":"5","key":"274_CR1","doi-asserted-by":"publisher","first-page":"1525","DOI":"10.1109\/TNET.2012.2232111","volume":"21","author":"PK Agarwal","year":"2013","unstructured":"Agarwal, P.K., Efrat, A., Ganjugunte, S.K., Hay, D., Sankararaman, S., Zussman, G.: The resilience of WDM networks to probabilistic geographical failures. IEEE\/ACM Trans. Netw. 21(5), 1525\u20131538 (2013)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"3","key":"274_CR2","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., Sharir, M.: Union of random Minkowski sums and network vulnerability analysis. Discrete Comput. Geom. 52(3), 551\u2013582 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"274_CR3","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Pach, J., Sharir, M.: State of the union (of geometric objects). In: Surveys on Discrete and Computational Geometry. Contemp. Math., vol. 453, pp. 9\u201348. Amer. Math. Soc., Providence (2008)","DOI":"10.1090\/conm\/453\/08794"},{"issue":"4","key":"274_CR4","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1007\/s4540010064","volume":"24","author":"PK Agarwal","year":"2000","unstructured":"Agarwal, P.K., Sharir, M.: Pipes, cigars, and kreplach: the union of Minkowski sums in three dimensions. Discrete Comput. Geom. 24(4), 645\u2013685 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"274_CR5","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Sharir, M., Steiger, A.: Decomposing the complement of the union of cubes in three dimensions. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (2021), pp. 1425\u20131444. SIAM, Philadelphia (2021)","DOI":"10.1137\/1.9781611976465.86"},{"issue":"4","key":"274_CR6","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s00454-006-1263-x","volume":"36","author":"B Aronov","year":"2006","unstructured":"Aronov, B., Efrat, A., Koltun, V., Sharir, M.: On the union of $$\\kappa $$-round objects in three and four dimensions. Discrete Comput. Geom. 36(4), 511\u2013526 (2006)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"274_CR7","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/BF02123007","volume":"10","author":"B Aronov","year":"1990","unstructured":"Aronov, B., Sharir, M.: Triangles in space or building (and analyzing) castles in the air. Combinatorica 10(2), 137\u2013173 (1990)","journal-title":"Combinatorica"},{"issue":"2","key":"274_CR8","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/BF02574371","volume":"12","author":"B Aronov","year":"1994","unstructured":"Aronov, B., Sharir, M.: Castles in the air revisited. Discrete Comput. Geom. 12(2), 119\u2013150 (1994)","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"274_CR9","doi-asserted-by":"publisher","first-page":"1785","DOI":"10.1137\/S0097539794266602","volume":"26","author":"B Aronov","year":"1997","unstructured":"Aronov, B., Sharir, M.: On translational motion planning of a convex polyhedron in $$3$$-space. SIAM J. Comput. 26(6), 1785\u20131803 (1997)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"274_CR10","doi-asserted-by":"publisher","first-page":"1670","DOI":"10.1137\/S0097539793250755","volume":"26","author":"B Aronov","year":"1997","unstructured":"Aronov, B., Sharir, M., Tagansky, B.: The union of convex polyhedra in three dimensions. SIAM J. Comput. 26(6), 1670\u20131688 (1997)","journal-title":"SIAM J. Comput."},{"key":"274_CR11","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.-T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific, Hackensack (2013)"},{"issue":"4","key":"274_CR12","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/PL00009366","volume":"19","author":"J-D Boissonnat","year":"1998","unstructured":"Boissonnat, J.-D., Sharir, M., Tagansky, B., Yvinec, M.: Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete Comput. Geom. 19(4), 485\u2013519 (1998)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"274_CR13","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1007\/s00454-016-9808-0","volume":"56","author":"H-C Chang","year":"2016","unstructured":"Chang, H.-C., 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."},{"issue":"5","key":"274_CR14","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4(5), 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"274_CR15","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s00454-010-9312-x","volume":"45","author":"E Ezra","year":"2011","unstructured":"Ezra, E.: On the union of cylinders in three dimensions. Discrete Comput. Geom. 45(1), 45\u201364 (2011)","journal-title":"Discrete Comput. Geom."},{"key":"274_CR16","doi-asserted-by":"crossref","unstructured":"Ezra, E., Sharir, M.: On the union of fat tetrahedra in three dimensions. J. ACM 57(1), #\u00a02 (2010)","DOI":"10.1145\/1613676.1613678"},{"issue":"3","key":"274_CR17","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0925-7721(02)00123-2","volume":"25","author":"MJ Golin","year":"2003","unstructured":"Golin, M.J., Na, H.-S.: On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes. Comput. Geom. 25(3), 197\u2013231 (2003)","journal-title":"Comput. Geom."},{"key":"274_CR18","volume-title":"Concrete Mathematics. A Foundation for Computer Science","author":"RL Graham","year":"1994","unstructured":"Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. A Foundation for Computer Science. Addison-Wesley, Reading (1994)"},{"issue":"3","key":"274_CR19","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":"274_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry. Graduate Texts in Mathematics","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002)"},{"issue":"1","key":"274_CR21","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s00454-003-2928-3","volume":"30","author":"J Pach","year":"2003","unstructured":"Pach, J., Safruti, I., Sharir, M.: The union of congruent cubes in three dimensions. Discrete Comput. Geom. 30(1), 133\u2013160 (2003)","journal-title":"Discrete Comput. Geom."},{"key":"274_CR22","doi-asserted-by":"crossref","unstructured":"Schneider, R., Wieacker, J.A.: Integral geometry. In: Handbook of Convex Geometry, vol. B, pp. 1349\u20131390. North-Holland, Amsterdam (1993)","DOI":"10.1016\/B978-0-444-89597-4.50022-6"},{"key":"274_CR23","volume-title":"Davenport\u2013Schinzel Sequences and Their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport\u2013Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)"},{"issue":"10","key":"274_CR24","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"DA Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76\u201384 (2009)","journal-title":"Commun. ACM"},{"key":"274_CR25","doi-asserted-by":"crossref","unstructured":"Weil, W., Wieacker, J.A.: Stochastic geometry. In: Handbook of Convex Geometry, vol.\u00a0B, pp. 1391\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":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00274-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-020-00274-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00274-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T15:37:26Z","timestamp":1619537846000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-020-00274-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,8]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["274"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00274-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,8]]},"assertion":[{"value":"18 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 December 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}