On optimal weighted balanced clusterings: Gravity bodies and power diagrams

Andreas Brieden, Peter Gritzmann

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

We study weighted clustering problems in Minkowski spaces under balancing constraints with a view towards separation properties. First, we introduce the gravity polytopes and more general gravity bodies that encode all feasible clusterings and indicate how they can be utilized to develop efficient approximation algorithms for quite general, hard to compute objective functions. Then we show that their extreme points correspond to strongly feasible power diagrams, certain specific cell complexes, whose defining polyhedra contain the clusters, respectively. Further, we characterize strongly feasible centroidal power diagrams in terms of the local optima of some ellipsoidal function over the gravity polytope. The global optima can also be characterized in terms of the separation properties of the corresponding clusterings.

Original languageEnglish
Pages (from-to)415-434
Number of pages20
JournalSIAM Journal on Discrete Mathematics
Volume26
Issue number2
DOIs
StatePublished - 2012

Keywords

  • Clustering
  • Constrained clustering
  • Gravity body
  • Gravity polytope
  • Power diagram
  • Weighted clustering

Fingerprint

Dive into the research topics of 'On optimal weighted balanced clusterings: Gravity bodies and power diagrams'. Together they form a unique fingerprint.

Cite this