Kolloquium SoSe 2014
When: Monday, 26.05.2014 – 17:15
Geometric Clustering for Land Consolidation
Authors: Steffen Borgwardt, Andreas Brieden and Peter Gritzmann
In many agricultural regions, a small group of farmers cultivates a large number of small, scattered lots. This leads to problems in the cost-effective structure of the region. The classical land consolidation is expensive and often lasts more than a decade. This is why the “voluntary land exchange” plays an increasingly important role as an alternative. It can be modeled as a clustering problem, which is NP-hard even in the simplemost cases.
For this problem, we devised an approach based on pushing apart the centers of gravity of the clusters. The approach combines
- the characterization of the extreme points of “gravity bodies”,
- modeling the “pushing”-part by a semi-norm,
- an efficient approximation of such a semi-norm by a polytope, only introducing a provably low approximation error, and
- determining the combinatorial diameter of the “partition polytopes”.
The methods have been implemented as software for practical applications, and have been complemented by economic evaluations, visualization and drag&drop-trading. It is used for schooling purposes and applied in agricultural and forest regions.
Steffen Borgwardt studied mathematics and computer science at the University of Augsburg and the Technische Universität München. In 2010, he completed his Ph.D. thesis on "A Combinatorial Optimization Approach to Constrained Clustering" in Prof. Peter Gritzmann's group for Applied Geometry and Discrete Mathematics.
His professional activities included the lead of an R&D-project for the Bavarian State, an acting professorship at the Technische Universität Braunschweig and a scholarship of the Humboldt-Foundation to work at the University of California, Davis, starting in September 2014.
He is particularly interested in real-world problems in the analysis of big data. His work with Peter Gritzmann and Andreas Brieden on clustering methods in the consolidation of farmland has been recognized with the European Excellence in Practice Award 2013.
Prof. Ulrike von Luxburg, ML