2026-10-15T07:59:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11558 2024-03-06T09:48:18Z ddc:004 open_access

Unbounded Regions of High-Order Voronoi Diagrams of Lines and Segments in Higher Dimensions Barequet, Gill Papadopoulou, Evanthia Suderland, Martin Voronoi diagram lines line segments higher-order order-k unbounded hypersphere arrangement great hyperspheres We study the behavior at infinity of the farthest and the higher-order Voronoi diagram of n line segments or lines in a d-dimensional Euclidean space. The unbounded parts of these diagrams can be encoded by a Gaussian map on the sphere of directions S^(d-1). We show that the combinatorial complexity of the Gaussian map for the order-k Voronoi diagram of n line segments or lines is O(min{k,n-k} n^(d-1)), which is tight for n-k = O(1). All the d-dimensional cells of the farthest Voronoi diagram are unbounded, its (d-1)-skeleton is connected, and it does not have tunnels. A d-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 lines has exactly n^2-n three-dimensional cells, when n >= 2. The Gaussian map of the farthest Voronoi diagram of line segments or lines can be constructed in O(n^(d-1) alpha(n)) time, while if d=3, the time drops to worst-case optimal O(n^2). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gill Barequet and Evanthia Papadopoulou and Martin Suderland 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.62 urn:nbn:de:0030-drops-115582 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.62 eng https://creativecommons.org/licenses/by/3.0/legalcode