Die Arbeit Minimum-link paths among obstacles in the plane behandelt das Problem, in einem mit polygonalen Möbeln vollgeräumten ebenen polygonalen Raum auf einem Polygonzug von A nach B zu gelangen und dabei möglichst wenige Knicke zu machen.
Die Arbeit Computing the geodesic center of a simple polygon behandelt das Standortproblem, auf einer polygonalen einfach zusammenhängenden Insel für eine Feuerwehrstation jenen Ort zu finden, von dem aus die Feuerwehr jeden Punkt der Insel auf dem Landweg in möglichst kurzer Zeit erreichen kann.
Die Arbeit Geometric clusterings behandelt das Problem der Clusteranalyse, eine Punktmenge in der Ebene in eine vorgegebene Anzahl von Klassen einzuteilen, sodass etwa der maximale Durchmesser der Klassen möglichst klein ist. Das Hauptergebnis dieser Arbeit ist die Aussage, dass sich in der Optimallösung die Klassen paarweise durch Geraden trennen lassen. Für die Zerlegung in drei Klassen wird der sich daraus ergebende Algorithmus in der Arbeit Three-clustering of points in the plane mit J. Hagauer durch besondere Zusatzüberlegungen stark verbessert.
Die Arbeit Shortest paths for line segments löst auf elementare Weise das von Stanislaw Ulam stammende Problem, eine Strecke auf der Ebene von einer gegebenen Ausgangslage so in eine gewünschte Ziellage zu bringen, dass die beiden Endpunkte insgesamt eine möglichst kurze Strecke zurücklegen.
Die folgenden Arbeiten behandeln geometrische Probleme aus der Mustererkennung, bei denen es darum geht, zwei gegebene Figuren durch Verschiebung oder Drehung möglichst gut zur Deckung zu bringen. Die kurze Arbeit Computing the minimum Hausdorff distance between two point sets on a line under translation löst das im Titel angegebene Problem mit einem einfachen und schnellen Algorithmus. In der Arbeit Matching shapes with a reference point wird die Heuristik untersucht, die für jede der beiden Figuren einen Referenzpunkt bestimmt und die beiden Referenzpunkte sodann einfach zur Deckung bringt. Als beste Wahl für den Referenzpunkt schlagen wir den sogenannten Steinerpunkt vor, der (zu Recht) nach dem Geometer Jakob Steiner benannt ist. Wir untersuchen, wie weit diese einfache Prozedur vom Optimum entfernt ist, und wir geben konstruktive untere Schranken für die Qualität von Referenzpunktmethoden an. Es ist bekannt, dass der Steinerpunkt (für die Minimierung des Hausdorff-Abstandes) tatsächlich der bestmögliche Referenzpunkt zur Mustererkennung ist. Die bekannten Beweise sind jedoch nicht konstruktiv. Ein anderes Abstandsmaß, nämlich die Fläche der symmetrischen Differenz, wird in der Arbeit Matching convex shapes with respect to the symmetric difference untersucht. Hier zeigt es sich, dass man den Schwerpunkt als Referenzpunkt verwenden kann.
Auch die Arbeit A new metric between polygons, and how to compute it hat mit Mustererkennung zu tun. Sie behandelt die sogenannte beschränkte Lipschitz-Norm, die ein Abstandsmaß zwischen Funktionen oder zwischen konvexen Bereichen der Ebene mit verschiedenen wünschenswerten Eigenschaften ist. Die beschränkte Lipschitz-Norm ist ein Spezialfall der Kantorowitsch-Rubinstein-Norm, die in der Wahrscheinlichkeitstheorie und in der Funktionentheorie auftritt. Die Kantorowitsch-Rubinstein-Norm wiederum geht auf Arbeiten von Kantorowitsch aus den 40er-Jahren und von Gaspard Monge aus dem 18. Jahrhundert über das Transportproblem zurück. In der Arbeit stelle ich verschiedene Formulierungen für die beschränkte Lipschitz-Norm dar, die zum Teil unabhängige Anwendungen haben, und ich gebe Algorithmen zur Berechnung der beschränkten Lipschitz-Norm an.
Die folgenden Arbeiten behandeln Triangulierungen ebener Punktmengen. In der Arbeit A simple linear time greedy triangulation algorithm for uniformly distributed points wird ein einfacher Algorithmus zur Bestimmung der Greedy-Triangulierung beschrieben, der im Erwartungswert lineare Laufzeit hat, wenn die Punkte gleichverteilt aus eine konvexen Menge gewählt werden. Im Gegensatz zu anderen bekannten Algorithmen, die dasselbe leisten, beruht unser Algorithmus auf einer tieferen Einsicht in die Struktur der Greedy-Triangulierung zufälliger Punktmengen und ist daher einfacher. In der Arbeit Constant-level greedy triangulations approximate the MWT well wird die Greedy-Triangulierung schichtweise konstruiert. Wenn man die Anzahl der Schichten kennt, kann man eine Approximationsschranke bezüglich der kürzesten Triangulierung angeben. Die Kernaussage der Arbeit Triangulations intersect nicely besagt, dass die Kanten zweier Triangulierungen einer Punktmenge immer so miteinander gepaart (gemätcht) werden können, dass je zwei einander zugeordneten Kanten sich schneiden oder zusammenfallen. Als Folgerungen ergeben sich verschiedene Möglichkeiten zur Berechnung unterer Schranken für die kürzeste Triangulierung (die Triangulierung mit der kleinsten Gesamtlänge aller Kanten). Wir hoffen, auf diesem Weg weiter Einsichten zur Berechnung der kürzesten Triangulierung zu gewinnen, ein Problem, dessen Komplexität bekanntlich offen ist.
Die Arbeit On-line q-adic covering by the method of the n-th segment and its application to on-line covering by cubes behandelt ein geometrisches Überdeckungsproblem, bei dem ein d-dimensionaler Einheitswürfel durch kleinere Würfel überdeckt werden soll. Die On-line-Beschränkung bedeutet dabei, dass die kleinen Würfel nur der Reihe nach bekannt werden und sofort endgültig platziert werden müssen. Wir führen dieses Problem auf ein eindimensionales "q-adisches" Intervallüberdeckungsproblem zurück. Daraus ergibt sich ein Algorithmus für das Würfelüberdeckungsproblem, der eine Überdeckung des Einheitswürfels garantiert, sobald das Gesamtvolumen der Würfel eine gewisse Schranke übersteigt. Ab d = 4 Dimensionen erhalten wir auf diese Art die besten bekannten Schranken, die nicht weit über den Schranken für das Off-line-Überdeckungsproblem liegen.
Die Serie der drei kleinen Arbeiten Counting k-subsets and convex k-gons in the plane, Counting convex k-gons in planar point sets und Counting convex polygons in planar point sets und die Arbeit Finding minimum area k-gons behandeln das Auffinden und Zählen von k-Ecken mit gewissen Eigenschaften in gegebenen ebenen Punktmengen.
Die Arbeit Shortest polygonal lines in space behandelt das auf Jakob Steiner zurückgehende Problem, den kürzesten Weg zu bestimmen, der jede Strecke eines gegebenen Streckenzuges in der vorgegebenen Reihenfolge besucht, in einigen Varianten.
Ein bekanntes Problem aus der Geometrie der Zahlen ist die Bestimmung eines kürzesten Vektors in einem Gitter. Die Arbeit Finding a shortest vector in a two-dimensional lattice modulo m zeigt, dass man eine Abwandlung dieses Problems, bei dem das Gitter auf einem Torus, das heißt modulo m, betrachtet wird, auf das klassische Problem zurückführen kann.
zum Überblick