People:	Prof. Dr. Peter Gritzmann, Dr. Steffen Borgwardt
Partners:	Prof. Dr. Andreas Brieden
Period:	2005 - today

Summary

The studies of special geometric bodies tied to constrained clustering of high-dimensional point sets lead to new and improved algorithms for the associated clustering problems. Each clustering of a weighted point set is associated to a gravity vector which lists the centers of gravity of the clusters. For fixed cluster sizes, the set of all gravity vectors yields a 'gravity polytope'. The vertices of such a polytope belong to clusterings that satisfy a very special separation property: They allow a generalized Voronoi diagram, called power diagram, of the underlying space such that each cluster lies in its own cell. We proved that such a clustering can be computed by linear programming over another geometric body, a 'partition polytope', and that a corresponding power diagram can also be computed efficiently. In the scope of this project, we transfer these algorithmic ideas to clustering problems for which the cluster sizes lie in between some given lower and upper bounds. The convex hull of the set of all gravity vectors constitutes a 'gravity body' in this case. These have a significantly more complex structure than the gravity polytopes they consist of, but their local extrema correspond to clusterings that not only again satisfy the above separation property, but have even further useful properties. Our research focuses on an analysis of the geometric structure of these gravity bodies, on the implications of their structure for the associated clustering problems, and on the development of improved and efficient approximation algorithms for constrained clustering based on linear and convex optimization over such bodies.

Selected Publications

• Steffen Borgwardt (2010) A Combinatorial Optimization Approach to Constrained Clustering. Ph.D. Thesis, TU München.
• Andreas Brieden and Peter Gritzmann (2011) On optimal weighted balanced clusterings: Gravity bodies and power diagrams, submitted manuscript, in review