Abstract: We shall tell the story of a very simple colouring algorithm the study of which will touch upon fields as diverse as graph theory, distributed computing, probabilistic algorithms, large deviation inequalities, the experimental analysis of algorithms, and approximation algorithms. During the discussion several (hopefully) interesting open problems will be presented. The talk describes joint work with: Devdatt Dubhashi, David Grable, Viggo Kann, Sanjeev Khanna, Jens Lagergren, Madhav Marathe, Larry Risinger and Riccardo Silvestri.
Abstract: In diesem Vortrag soll der Zusammenhang zwischen einigen Extremalproblemen der kombinatorischen Geometrie (etwa: wie oft kann derselbe Abstand unter n Punkten in der Ebene vorkommen?) und algorithmischen Problemen der Punktmustererkennung dargestellt werden. Hier tauchen eine Reihe klassischer Erdös-Probleme in Varianten wieder auf, denn die schwierigen Situationen für die Mustererkennung sind gerade die, in denen Teile des Musters sehr oft in der Punktmenge auftauchen, so daß es viele 'potentielle Treffer' gibt, die alle untersucht werden müssen. Dies soll besonders am Problem der Erkennung dreidimensionaler Teilmuster dargestellt werden, für das ich einen neuen Algorithmus angebe. Dieser liefert gleichzeitig eine neue Schranke für die Maximalzahl kongruenter Dreiecke in einer Menge von n Punkten im dreidimensionalen Raum, ein Problem, das Erdös und Purdy 1971 gestellt haben.