k-set polytopes and order-k Delaunay diagrams

Given a set S of n points (called sites) in a d-dimensional Euclidean space E and an integer k, 1 les k les n - 1, we consider three known structures that are defined through subsets of k elements of S: The k-set polytope of S, the order-k Voronoi diagram of S, and its dual, the order-k Delaunay diagram of S. We give a new compact characterization of all-dimensional faces of these three structures through the notions of k-couple and of k-set polytope of a k-couple. We also show that the incidence relations between these faces correspond to inclusion relations between k-couples. These characterizations allow us to give simple proofs of well known relations between the three structures, especially that the d-dimensional order-k Delaunay diagram is the projection of the lower hull of a (d + 1)- dimensional k-set polytope and is the orthogonal dual of the order-k Voronoi diagram.