Die Arbeit On the union of fat wedges and separating a collection of segments by a line wird das geometrische Problem untersucht, wie viele Komponenten übrigbleiben können, wenn man von der Ebene die Vereinigung von n Dreiecken entfernt, deren Winkel alle mindestens α sind. (Für α= 0 kann man klarerweise O(n^2 ) Komponenten bekommen.) Ähnlich wie in der Arbeit Simultaneous inner and outer approximation of shapes ist dieses Problem wieder von dem Ansatz motiviert, die Laufzeit von Algorithmen nicht nur für den schlechtesten Fall zu bestimmen, sondern auch für "vernünftige" Eingaben. In unserem Fall bedeutet vernünftig, dass die Dreiecke nicht beliebig lang und dünn sein dürfen.
Die Arbeit Degenerate convex hulls in high dimensions without extra storage behandelt das grundlegende Problem, die Ecken eines als Schnitt von Halbräumen gegebenen Polyeders beziehungsweise die Facetten der konvexen Hülle einer gegebenen Punktmenge aufzuzählen. (Diese beiden Probleme sind geometrisch dual zueinander und rechnerisch gleichwertig.) In Abwandlung eines Algorithmus von Avis und Fukuda, der dieses Problem ohne zusätzlichen Speicherbedarf löst, habe ich ein Verfahren vorgeschlagen, das besonders auf Eingaben in spezieller Lage zugeschnitten ist.
Die Arbeit Maintaining the approximate width of a set of points in the plane zeigt, wie man die Breite einer Punktmenge (den kleinsten Abstand zwischen zwei parallelen Geraden, die die Punktmenge einschließen) nach dem Hinzufügen oder Wegnehmen eines Punktes neu bestimmen kann, ohne sie jedesmal ganz von vorne auszurechnen. Für die exakte Breite ist dieses Problem schwierig; daher haben wir uns mit einer Näherung für die Breite zufriedengegeben.
In den Bereich der rechnerischen Geometrie fallen auch meine Arbeiten zu geometrischen Optimierungsproblemen, insbesondere die Arbeiten zum Rundreiseproblem.
zum Überblick