Barequet Gill, Papadopoulou Evanthia, Suderland Martin
Dept. of Computer Science, The Technion - Israel Inst. of Technology, Haifa, 3200003 Israel.
Faculty of Informatics, Università della Svizzera italiana, 6900 Lugano, Switzerland.
Discrete Comput Geom. 2024;72(3):1304-1332. doi: 10.1007/s00454-023-00492-2. Epub 2023 May 25.
We study the behavior at infinity of the farthest and the higher-order Voronoi diagram of line segments or lines in a -dimensional Euclidean space. The unbounded parts of these diagrams can be encoded by a on the sphere of directions . We show that the combinatorial complexity of the Gaussian map for the order- Voronoi diagram of line segments and lines is , which is tight for . This exactly reflects the combinatorial complexity of the unbounded features of these diagrams. All the -dimensional cells of the farthest Voronoi diagram are unbounded, its -skeleton is connected, and it does not have tunnels. A -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 in general position has exactly three-dimensional cells. The Gaussian map of the farthest Voronoi diagram of line segments and lines can be constructed in time, for , while if , the time drops to worst-case optimal . We extend the obtained results to bounded polyhedra and clusters of points as sites.
我们研究了(n)维欧几里得空间中线段或直线的最远和高阶Voronoi图在无穷远处的行为。这些图的无界部分可以通过方向球面(S^{n - 1})上的一个高斯映射进行编码。我们证明，线段和直线的(k)阶Voronoi图的高斯映射的组合复杂度为(\Theta(n^{k}))，对于(k\geq1)是紧的。这准确地反映了这些图的无界特征的组合复杂度。最远Voronoi图的所有(n)维单元都是无界的，其((n - 1))骨架是连通的，并且没有隧道。如果Voronoi图的一个(n)单元的无界方向集（表示为其高斯映射上的点）不连通，则称该(n)单元为隧道。在三维空间中，处于一般位置的(n)条直线的最远Voronoi图恰好有(\frac{n(n - 1)(n - 2)}{6})个三维单元。对于(k\geq1)，线段和直线的最远Voronoi图的高斯映射可以在(O(n^{k + 1}))时间内构造，而如果(k = 0)，时间降至最坏情况最优的(O(n^2))。我们将所得结果扩展到有界多面体和作为站点的点簇。
