论文库

原文摘要

We study nearest and farthest Voronoi diagrams of lines in three-dimensional Euclidean space, which partition space according to the closest and farthest input lines, respectively. For arbitrary lines, a gap remains between the known quadratic lower bound and near-cubic upper bounds for the complexity of the nearest diagram. We consider input lines chosen from one of two continuous families of straight lines on a smooth surface defined by a quadratic equation, with one line from each family passing through every point of the surface. Under the geometric assumptions stated in the paper, we prove quadratic upper bounds on the total number of vertices, edges, faces, and connected three-dimensional regions in both diagrams. We also construct quadratically many nearest vertices using lines from a single family on one fixed surface, establishing a tight quadratic worst-case bound. The farthest diagram has quadratic total complexity for every input satisfying our assumptions. Our proof uses a parametrization that arranges the input lines in a cyclic order and expresses tangency to a sphere by a polynomial equation of degree four. At a Voronoi vertex, the four tangent input lines give four distinct roots. The sign changes between these roots, together with the nearest or farthest condition, force two intervening parameter intervals to contain no other input parameters. Thus, only quadratically many choices of four lines can define a vertex, and each choice yields at most eight isolated candidate centers.