Diskrete Geometrie

In der Schulgeometrie sind Linien und Flächen glatt und lückenlos. Eine Gerade besteht dort aus unendlich vielen Punkten, die nahtlos ineinander übergehen. Die diskrete Geometrie geht anders vor: Sie betrachtet abzählbar viele einzelne Objekte, etwa hundert Punkte auf einem Blatt Papier oder die Ecken eines Würfels. Das Wort « diskret » bedeutet hier « getrennt », « einzeln abzählbar » – es hat nichts mit Verschwiegenheit zu tun. Typische Fragen lauten: Wie viele Geraden lassen sich durch eine gegebene Punktmenge legen? Wie dicht kann man gleich große Kugeln in einen Karton packen? Es geht also weniger um Messen und mehr um Zählen, Anordnen und Vergleichen.

Warum Computer nur mit Punkten rechnen können

Ein Computer kann keine unendlich feinen Linien speichern. Sein Speicher ist begrenzt, und jede Zahl belegt eine feste Anzahl an Bits. Deshalb wird alles Räumliche in endlich viele Bausteine zerlegt. Ein Bildschirm besteht aus Pixeln, ein 3D-Modell aus Dreiecken, eine Landkarte aus Koordinatenpunkten. Genau das ist der Gegenstand der diskreten Geometrie.

Dadurch wird sie zur Werkzeugkiste für viele technische Bereiche. Computergrafik, Bildverarbeitung, Robotik und Chipdesign greifen auf ihre Ergebnisse zurück. Auch die Frage, wie ein Navigationssystem den kürzesten Weg findet, hat einen diskret-geometrischen Kern. Die Straßen sind dabei Kanten, die Kreuzungen sind Punkte.

Ein zweiter Grund ist wirtschaftlicher Natur. Viele Packungs- und Zuschnittprobleme sind diskrete Geometrie in reiner Form. Wie viele Bauteile passen auf eine Metallplatte, ohne dass Verschnitt entsteht? Wie stapelt man Container auf einem Schiff möglichst platzsparend? Ein paar Prozent bessere Anordnung bedeuten hier direkt gesparte Kosten.

Zählen, Zerlegen und Optimieren

Die diskrete Geometrie arbeitet fast immer mit endlichen Mengen von Objekten. Ein klassisches Werkzeug ist die Triangulierung: Eine Fläche wird lückenlos in Dreiecke zerlegt. Dreiecke sind praktisch, weil sie immer eben sind und sich leicht berechnen lassen. Deshalb bestehen 3D-Modelle in Spielen und Filmen aus Millionen kleiner Dreiecke.

Ein weiteres Standardwerkzeug ist die konvexe Hülle. Man stellt sich vor, ein Gummiband wird um eine Punktwolke gespannt. Die Form, die dabei entsteht, ist die konvexe Hülle. Sie beschreibt die äußere Begrenzung einer Menge von Punkten und lässt sich vom Computer schnell berechnen. Solche Verfahren sind Bausteine für Kollisionserkennung in Spielen oder für die Analyse von Messdaten.

Typisch für das Gebiet sind außerdem Beweise über Grenzen. Mathematiker fragen nicht nur, wie eine gute Anordnung aussieht, sondern auch, ob es überhaupt eine bessere geben kann. Die Kepler-Vermutung zur dichtesten Kugelpackung wurde erst 1998 mit Computerhilfe bewiesen. Das zeigt: Auch scheinbar einfache Fragen können jahrhundertelang offen bleiben.

Von Videospielen bis zur Mustererkennung

Am sichtbarsten wird das Gebiet in der Computergrafik. Jede Spielfigur ist ein Netz aus Dreiecken, jede Kamerabewegung eine geometrische Rechnung. Auch 3D-Drucker zerlegen ein Objekt in Schichten und Bahnen. Wer eine Datei für den Druck vorbereitet, arbeitet unbewusst mit diskreter Geometrie.

In der künstlichen Intelligenz taucht das Gebiet indirekt auf. Daten werden oft als Punkte in einem hochdimensionalen Raum dargestellt. Verfahren wie das Gruppieren ähnlicher Datenpunkte, das sogenannte Clustering, beruhen auf Abständen zwischen diesen Punkten. Auch Nachbarschaftssuchen in großen Datenbanken nutzen Strukturen aus der diskreten Geometrie. Selbstfahrende Autos verarbeiten damit die Punktwolken ihrer Laserscanner.

Ein häufiger Irrtum ist, diskrete Geometrie sei nur eine ungenaue Näherung der « echten » Geometrie. Das stimmt nicht. Sie ist ein eigenständiges Forschungsgebiet mit eigenen Sätzen und offenen Problemen. In Nachrichten begegnet man ihr meist versteckt, etwa wenn von neuen Rekorden bei Packungsproblemen oder von schnelleren Grafikverfahren berichtet wird.