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 full cell decomposition) can be computed by solving a linear program over the 'partition polytope'. This leads to efficient data classification and prediction algorithms. We then study the edge-structure of the two polytopes and derive a tight upper bound on the combinatorial diameter of the partition polytope. Finally, inspired by our polytopal studies, we devise a combinatorial optimization model for our real-world problem.     «

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...     »

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 Schwerpunktpolytops durch ein lineares Optimierungsproblem im 'Partitionspolytop' berechnet werden kann. Dies führt zu effizienten Datenklassifikations- und Vorhersagealgorithmen. Außerdem untersuchen wir die Kantenstruktur der beiden Polytope und leiten eine scharfe obere Schranke für den kombinatorischen Durchmesser des Partitionspolytops her. Abschließend leiten wir ein kombinatorisches Optimierungsmodell für unsere Praxisanwendung aus unseren polytopalen Studien ab.     «

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...     »