On optimal weighted balanced clusterings: gravity bodies and power diagrams (Q2910923)

The paper is a thorough theoretical study on weighted balanced clustering in Minkowski spaces. Gravity polytopes are introduced and it is illustrated that each such fractional clustering admits a Voronoi dissection of the space; a polyhedral cell complex contains the clusters and the extreme points actually correspond to strongly feasible power diagrams. The strongly feasible centroidal power diagrams are considered in terms of local maxima of a convex ellipsoidal function over gravity polytopes, while the global maxima are characterized in reference to separation properties of the clusterings. While the many concepts and proofs address an audience in theoretical computer science, practitioners will find the article useful through the reference to the new approach to the real-world problem of farm consolidation based on lend-lease agreements.