Unbounded Regions of High-Order Voronoi Diagrams of Lines and Line Segments in Higher Dimensions.

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.