{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:19Z","timestamp":1740109579902,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T00:00:00Z","timestamp":1684972800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T00:00:00Z","timestamp":1684972800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021E-201356"],"award-info":[{"award-number":["200021E-201356"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2017684"],"award-info":[{"award-number":["2017684"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,10]]},"abstract":"Abstract<\/jats:title>We study the behavior at infinity of the farthest and the higher-order Voronoi diagram of\u00a0n<\/jats:italic> line segments or lines in a d<\/jats:italic>-dimensional Euclidean space. The unbounded parts of these diagrams can be encoded by a Gaussian map<\/jats:italic> on the sphere of directions\u00a0$$\\mathbb {S}^{d-1}$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n <\/mml:mrow>\n \n d<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We show that the combinatorial complexity of the Gaussian map for the order-k<\/jats:italic> Voronoi diagram of\u00a0n<\/jats:italic> line segments and lines is $$O(\\min \\{k,n-k\\}n^{d-1})$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n min<\/mml:mo>\n \n {<\/mml:mo>\n k<\/mml:mi>\n ,<\/mml:mo>\n n<\/mml:mi>\n -<\/mml:mo>\n k<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n \n d<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is tight for $$n-k=O(1)$$<\/jats:tex-math>\n \n n<\/mml:mi>\n -<\/mml:mo>\n k<\/mml:mi>\n =<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This exactly reflects the combinatorial complexity of the unbounded features of these diagrams. All the d<\/jats:italic>-dimensional cells of the farthest Voronoi diagram are unbounded, its $$(d-1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n d<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-skeleton is connected, and it does not have tunnels. A d<\/jats:italic>-cell of the Voronoi diagram is called a tunnel if the set of its unbounded directions, represented as points on its Gaussian map, is not connected. In a three-dimensional space, the farthest Voronoi diagram of \u00a0$$n \\ge 2$$<\/jats:tex-math>\n \n n<\/mml:mi>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> lines in general position has exactly $$n(n-1)$$<\/jats:tex-math>\n \n n<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> three-dimensional cells. The Gaussian map of the farthest Voronoi diagram of line segments and lines can be constructed in $$O(n^{d-1} \\alpha (n))$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n d<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \u03b1<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, for $$d\\ge 4$$<\/jats:tex-math>\n \n d<\/mml:mi>\n \u2265<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, while if $$d=3$$<\/jats:tex-math>\n \n d<\/mml:mi>\n =<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the time drops to worst-case optimal\u00a0$$\\Theta (n^2)$$<\/jats:tex-math>\n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We extend the obtained results to bounded polyhedra and clusters of points as sites.<\/jats:p>","DOI":"10.1007\/s00454-023-00492-2","type":"journal-article","created":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T19:01:40Z","timestamp":1685041300000},"page":"1304-1332","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Unbounded Regions of High-Order Voronoi Diagrams of Lines and Line Segments in Higher Dimensions"],"prefix":"10.1007","volume":"72","author":[{"given":"Gill","family":"Barequet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0144-7384","authenticated-orcid":false,"given":"Evanthia","family":"Papadopoulou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6604-6381","authenticated-orcid":false,"given":"Martin","family":"Suderland","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,25]]},"reference":[{"key":"492_CR1","unstructured":"Abellanas, M., Hurtado, F., Icking, Ch., Klein, R., Langetepe, E., Ma,\u00a0L., Palop,\u00a0B., Sacrist\u00e1n,\u00a0V.: The farthest color Voronoi diagram and related problems (extended abstract). In: 17th European Workshop Comput. Geom. (Berlin 2001), pp. 113\u2013116. http:\/\/www.pi6.fernuni-hagen.de\/downloads\/publ\/ahiklmps-fcvdr-01.pdf"},{"issue":"3","key":"492_CR2","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1137\/S0097539795281840","volume":"27","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., de Berg, M., Matou\u0161ek, J., Schwarzkopf, O.: Constructing levels in arrangements and higher order Voronoi diagrams. SIAM J. Comput. 27(3), 654\u2013667 (1998)","journal-title":"SIAM J. Comput."},{"key":"492_CR3","unstructured":"Agarwal, P.K., Sharir, M.: Arrangements and their applications. In: Handbook of Computational Geometry, pp. 49\u2013119. North-Holland, Amsterdam (2000)"},{"issue":"4","key":"492_CR4","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0020-0190(01)00336-2","volume":"83","author":"B Aronov","year":"2002","unstructured":"Aronov, B.: A lower bound on Voronoi diagram complexity. Inform. Process. Lett. 83(4), 183\u2013185 (2002)","journal-title":"Inform. Process. Lett."},{"issue":"6","key":"492_CR5","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.ipl.2006.07.008","volume":"100","author":"F Aurenhammer","year":"2006","unstructured":"Aurenhammer, F., Drysdale, R.L.S., Krasser, H.: Farthest line segment Voronoi diagrams. Inform. Process. Lett. 100(6), 220\u2013225 (2006)","journal-title":"Inform. Process. Lett."},{"key":"492_CR6","unstructured":"Aurenhammer, F., J\u00fcttler, B., Paulini, G.: Voronoi diagrams for parallel halflines and line segments in space. In: 28th International Symposium on Algorithms and Computation (Phuket 2017). Leibniz Int. Proc. Inform., vol. 92, #\u00a07. Leibniz-Zent. Inform., Wadern (2017)"},{"key":"492_CR7","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":"8","key":"492_CR8","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1016\/j.comgeo.2014.04.005","volume":"47","author":"SW Bae","year":"2014","unstructured":"Bae, S.W.: Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments. Comput. Geom. 47(8), 779\u2013788 (2014)","journal-title":"Comput. Geom."},{"key":"492_CR9","doi-asserted-by":"crossref","unstructured":"Barequet, G., Papadopoulou, E.: On the farthest-neighbor Voronoi diagram of segments in three dimensions. In: 10th International Symposium on Voronoi Diagrams in Science and Engineering (St. Petersburg 2013), pp. 31\u201336. IEEE Computer Society, Washington (2013)","DOI":"10.1109\/ISVD.2013.15"},{"key":"492_CR10","unstructured":"Barequet, G., Papadopoulou, E., Suderland, M.: Unbounded regions of high-order Voronoi diagrams of lines and segments in higher dimensions. In: 30th International Symposium on Algorithms and Computation (Shanghai 2019). Leibniz Int. Proc. Inform., vol. 149, #\u00a062. Leibniz-Zent. Inform., Wadern (2019)"},{"key":"492_CR11","doi-asserted-by":"crossref","unstructured":"Chazelle, B.: An optimal convex hull algorithm and new results on cuttings. In: 32nd Annual Symposium on Foundations of Computer Science (San Juan 1991), pp. 29\u201338. IEEE Computer Society, Washington (1991)","DOI":"10.1109\/SFCS.1991.185345"},{"issue":"2","key":"492_CR12","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1998.0957","volume":"29","author":"LP Chew","year":"1998","unstructured":"Chew, L.P., Kedem, K., Sharir, M., Tagansky, B., Welzl, E.: Voronoi diagrams of lines in 3-space under polyhedral convex distance functions. J. Algorithms 29(2), 238\u2013255 (1998)","journal-title":"J. Algorithms"},{"issue":"5","key":"492_CR13","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":"4","key":"492_CR14","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/BF02187733","volume":"4","author":"H Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L.J., Sharir, M.: The upper envelope of piecewise linear functions: algorithms and applications. Discrete Comput. Geom. 4(4), 311\u2013336 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"492_CR15","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02187681","volume":"1","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Seidel, R.: Voronoi diagrams and arrangements. Discrete Comput. Geom. 1(1), 25\u201344 (1986)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"492_CR16","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1137\/0222031","volume":"22","author":"H Edelsbrunner","year":"1993","unstructured":"Edelsbrunner, H., Seidel, R., Sharir, M.: On the zone theorem for hyperplane arrangements. SIAM J. Comput. 22(2), 418\u2013429 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"492_CR17","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00454-009-9173-3","volume":"42","author":"H Everett","year":"2009","unstructured":"Everett, H., Lazard, D., Lazard, S., Safey El Din, M.: The Voronoi diagram of three lines. Discrete Comput. Geom. 42(1), 94\u2013130 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"492_CR18","unstructured":"Halperin, D., Sharir, M.: Arrangements. In: Handbook of Discrete and Computational Geometry, pp. 723\u2013762. Chapman & Hall\/CRC, Boca Raton (2018)"},{"key":"492_CR19","doi-asserted-by":"crossref","unstructured":"Hemmer, M., Setter, O., Halperin, D.: Constructing the exact Voronoi diagram of arbitrary lines in three-dimensional space with fast point-location. In: 18th Annual European Symposium on Algorithms (Liverpool 2010). Part\u00a0I. Lecture Notes in Comput. Sci., vol. 6346, pp. 398\u2013409. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-15775-2_34"},{"issue":"3","key":"492_CR20","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BF02189323","volume":"9","author":"DP Huttenlocher","year":"1993","unstructured":"Huttenlocher, D.P., Kedem, K., Sharir, M.: The upper envelope of Voronoi surfaces and its applications. Discrete Comput. Geom. 9(3), 267\u2013291 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"492_CR21","doi-asserted-by":"crossref","unstructured":"Klee, V.: On the complexity of d-dimensional Voronoi diagrams. Arch. Math. (Basel) 34(1), 75\u201380 (1980)","DOI":"10.1007\/BF01224932"},{"issue":"3","key":"492_CR22","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1137\/S0097539702408387","volume":"32","author":"V Koltun","year":"2003","unstructured":"Koltun, V., Sharir, M.: 3-dimensional Euclidean Voronoi diagrams of lines with a fixed number of orientations. SIAM J. Comput. 32(3), 616\u2013642 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"492_CR23","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s00454-003-2950-5","volume":"31","author":"V Koltun","year":"2004","unstructured":"Koltun, V., Sharir, M.: Polyhedral Voronoi diagrams of polyhedra in three dimensions. Discrete Comput. Geom. 31(1), 83\u2013124 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"492_CR24","volume-title":"Topology","author":"K Kuratowski","year":"1966","unstructured":"Kuratowski, K.: Topology, vol. 1. Academic Press, New York (1966)"},{"key":"492_CR25","doi-asserted-by":"crossref","unstructured":"Mantas, I., Papadopoulou, E., Sacrist\u00e1n, V., Silveira, R.I.: Farthest color Voronoi diagrams: complexity and algorithms. In: 14th Latin American Symposium on Theoretical Informatics (S\u00e3o Paulo 2021). Lecture Notes in Comput. Sci., vol. 12118, pp. 283\u2013295. Springer, Cham (2020)","DOI":"10.1007\/978-3-030-61792-9_23"},{"issue":"2","key":"492_CR26","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1112\/S0025579300002850","volume":"17","author":"P McMullen","year":"1970","unstructured":"McMullen, P.: The maximum numbers of faces of a convex polytope. Mathematika 17(2), 179\u2013184 (1970)","journal-title":"Mathematika"},{"issue":"5","key":"492_CR27","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1142\/S0218195901000651","volume":"11","author":"JSB Mitchell","year":"2001","unstructured":"Mitchell, J.S.B., O\u2019Rourke, J.: Computational geometry column 42. Int. J. Comput. Geom. Appl. 11(5), 573\u2013582 (2001)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"4","key":"492_CR28","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF02574692","volume":"6","author":"K Mulmuley","year":"1991","unstructured":"Mulmuley, K.: On levels in arrangements and Voronoi diagrams. Discrete Comput. Geom. 6(4), 307\u2013338 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"492_CR29","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s00453-004-1095-0","volume":"40","author":"E Papadopoulou","year":"2004","unstructured":"Papadopoulou, E.: The Hausdorff Voronoi diagram of point clusters in the plane. Algorithmica 40(2), 63\u201382 (2004)","journal-title":"Algorithmica"},{"issue":"6","key":"492_CR30","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1142\/S0218195904001536","volume":"14","author":"E Papadopoulou","year":"2004","unstructured":"Papadopoulou, E., Lee, D.T.: The Hausdorff Voronoi diagram of polygonal objects: a divide and conquer approach. Int. J. Comput. Geom. Appl. 14(6), 421\u2013452 (2004)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"492_CR31","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/s00453-014-9950-0","volume":"74","author":"E Papadopoulou","year":"2016","unstructured":"Papadopoulou, E., Zavershynskyi, M.: The higher-order Voronoi diagram of line segments. Algorithmica 74(1), 415\u2013439 (2016)","journal-title":"Algorithmica"},{"key":"492_CR32","doi-asserted-by":"crossref","unstructured":"Seidel, R.: On the number of faces in higher-dimensional Voronoi diagrams. In: 3rd Annual Symposium on Computational Geometry (Waterloo 1987), pp. 181\u2013185. ACM, New York (1987)","DOI":"10.1145\/41958.41977"},{"issue":"3","key":"492_CR33","doi-asserted-by":"publisher","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(3), 327\u2013345 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"492_CR34","doi-asserted-by":"crossref","unstructured":"Stanley, R.P.: An introduction to hyperplane arrangements. In: Geometric Combinatorics. IAS\/Park City Math. Ser., vol. 13, pp. 389\u2013496. American Mathematical Society, Providence (2007)","DOI":"10.1090\/pcms\/013\/08"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00492-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00492-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00492-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T02:02:37Z","timestamp":1728180157000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00492-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,25]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["492"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00492-2","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,5,25]]},"assertion":[{"value":"24 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 October 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}