Order-k Voronoi Diagrams, k-Sections, and k-Sets

In this paper we characterize all-dimensional faces of order-k Voronoi diagrams. First we introduce the notion of k-section to give a precise definition of these faces. Then, we characterize the unbounded faces by extending the classical notion of k-set. Finally, by studying some relations between k-sections, we give a new proof of the size of order-k Voronoi diagrams in the plane.