Constrained Clustering, Diagrams, Coresets, and Their Applications
摘要
We study geometric diagrams and their relation to constrained clustering with a view towards applications in agriculture (consolidation of farmland), political science (electoral districting) and materials science (representation of polycrystalline materials). For the latter, weight-constrained anisotropic clustering allows to compute diagram respresentations from data on the volume, center and second-order moments of the grains which are available through tomographic measurements. Also we present new coreset techniques, interesting in their own right, which are utilized to significantly accelerate the computations. This effect is demonstrated on 3D real-world data sets from materials science.