Clustering and triangulation problems

Research project P 14755 Clustering and Triangulation Problems Franz AURENHAMMER 27.11.2000 The aim of this project is the investigation and development of methods for clustering and triangulating data point sets. Clustering a set of data means grouping the set into subsets (clusters) such that members of the same cluster are similar, and members of different clusters are dissimilar, according to a predefined similarity measure. Triangulating a set of data points in the Euclidean plane means constructing a triangular mesh which uses all and only these points, and which is optimum with respect to a given criterion. These problems belong to the class of geometric optimization problems. They are partially interrelated and have a long history. In spite of the remarkable international efforts that have been made on these subjects, practically efficient solutions are hard to obtain in several cases (e.g. approximations for certain NP-hard clustering problems, or for uniform triangulations), or even the complexity status is unsolved (e.g. minimum-weight triangulation problem). Our main objective is to investigate the combinatorial and geometric properties of such problems, in order to design practically efficient algorithms. Particular topics to be investigated include: (1) Morphing of spanning trees via Delaunay triangulations, using an efficient method developed in our prework. Applications to be worked out are clustering pre-separated point sets, mesh. coarsening, and morphing of graphical objects. (2) Deciding the existence of compatible triangulations for two given data point sets. A result of this kind, apart from its theoretical value, would pave the way for a general method for morphing graphical objects. Our prework proves the result true for small point sets and for point sets with few interior points. (3) Optimal triangulations. The two well-known representatives of optimal triangulations, the Delaunay and the minimum-weight triangulation, show certain disadvantages in practical situations. As an alternative, we introduce minimum-stress triangulations, where the stress of a data point is an appropriate function of its incident triangulation edges. This concept simulates equilibrium state at each data point as much as possible, and is a promising candidate in quality mesh generation.