User: Guest  Login
Original title:
A Combinatorial Optimization Approach to Constrained Clustering 
Translated title:
Clustering unter Nebenbedingungen aus der Sicht der kombinatorischen Optimierung 
Year:
2010 
Document type:
Dissertation 
Institution:
Fakultät für Mathematik 
Advisor:
Gritzmann, Peter (Prof. Dr.) 
Referee:
Gritzmann, Peter (Prof. Dr.); Rothblum, Uriel G. (Prof. Dr.); Brokate, Martin (Prof. Dr.) 
Language:
en 
Subject group:
MAT Mathematik 
Abstract:
Motivated by an application in the consolidation of farmland, we study two polytopes tied to the clustering of a geometric point set into clusters of prescribed sizes. First, we characterize the vertices of the 'gravity polytope' as belonging to clusterings that allow a 'full cell decomposition' of the underlying space such that each cluster lies in its own cell. Hereby we obtain an alternative characterization of power diagrams. We show that a vertex of the gravity polytope (and a corresponding...    »
 
Translated abstract:
Ausgehend von einer Anwendung in der Flurbereinigung untersuchen wir zwei Polytope, die mit dem Partitionieren einer geometrischen Punktmenge in Cluster vorgeschriebener Größen zusammenhängen. Wir charakterisieren die Ecken des 'Schwerpunktpolytops' als assoziiert zu Clusterings, die eine 'volle Zellzerlegung' erlauben, so dass jeder Cluster in seiner eigenen Zelle liegt. Hierdurch erhalten wir eine alternative Charakterisierung von Power-Diagrammen. Wir zeigen, dass eine Ecke des Schwerpunktpol...    »
 
Oral examination:
23.12.2010 
File size:
3719879 bytes 
Pages:
224 
Last change:
24.01.2011