Given a set V of n points in the plane, we introduce a new number of k-sets that is an invariant of V: the number of k-sets of a convex inclusion chain of V. A convex inclusion chain of V is an ordering (v 1 , v 2 ,...,v n ) of the points of V such that no point of the ordering belongs to the convex hull of its predecessors. The k-sets of such a chain are then the distinct k-sets of all the subsets {v 1 ,...,v i }, for all i in {k + 1,..., n}. We show that the number of these k-sets depends only on V and not on the chosen convex inclusion chain. Moreover, this number is surprisingly equal to the number of regions of the order-k Voronoi diagram of V. As an application, we give an efficient on-line algorithm to compute the k-sets of the vertices of a simple polygonal line, no vertex of which belonging to the convex hull of its predecessors on the line.
['Wael El Oraiby', 'Dominique Schmitt']
k-sets of convex inclusion chains of planar point sets