Topology-Preserving Distance Functions for Tessellations

H. Hagen, M. Ruby, I. Scheler, and M. Schneider (Germany)


Environmental Sciences Visualization, Multidimensional Visualization, Geospatial Science, Generalized Distance Functions, Region Clustering


Clustering and classification of datasets is an important problem in many application fields, most often to be solved in order to determine specific regions of interest. Com monly, the topology of the dataset has to be preserved, im plying that unconnected parts of a cluster (so-called holes) have to be avoided. We develop a new Voronoi clustering technique based on the k-means scheme. For this purpose, we construct gen eralized distance functions that guarantee topological cor rectness. The distance functions are given by a custom definition of the unit neighborhood of seed points. Us ing a region-growing algorithm that is independent of the used distance function and specific weighting, we arrive at a flexible and general topology-preserving clustering method. We apply our scheme to several both multi-dimensional and scattered data examples from the field of geospatial planning and urban development. However, the domain independent algorithm can easily be used in many other clustering and classification tasks.

Important Links:

Go Back