scientific article; zbMATH DE number 108318

Publication date 23 January 1993

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

Das Voronoi-Diagramm von \(n\) Objekten \(p_ 1,...,p_ n\) ist eine Partition der euklidischen Ebene in Regionen, je eine zu jedem \(p_ i\), so daß die Region von \(p_ i\) alle Punkte der Ebene enthält, die näher bei \(p_ i\) liegen als bei jedem anderen \(p_ j\). Voronoi-Diagramme wurden zuerst für Gitterpunkte in der Zahlentheorie betrachtet; wegen ihrer zahlreichen Anwendungen spielen sie heute eine herausragende Rolle in der Informatik, besonders in der Algorithmischen Geometrie und der Bewegungsplanung, aber auch in anderen Wissenschaften. Das Problem besteht darin, das Voronoi-Diagramm möglichst schnell und mit möglichst wenig Speicherplatz zu berechnen. Hierzu ist die Kenntnis seiner strukturellen Eigenschaften erforderlich. In den letzten 15 Jahren wurden in der Literatur zahlreiche Varianten des Voronoi-Diagramms studiert, die sich durch Wahl von Objekten \(p_ i\) verschiedenen Typs, durch Zugrundelegen eines nicht-euklidischen Abstandsbegriffs oder in höherdimensionalen Räumen ergeben. Eine weitere wichtige Verallgemeinerung besteht in den Voronoi-Diagrammen \(k\)- ter Ordnung, bei denen jeder Teilmenge von \(k\) Objekten die Region derjenigen Punkte zugeordnet wird, die näher an jedem dieser \(k\) Objekte liegen als an jedem der übrigen \(n-k\). Nachdem zunächst nur die Verhältnisse im statischen Fall, wo alle \(n\) Objekte von vornherein bekannt sind, untersucht worden waren, hat man sich in den letzten 4 Jahren mit der dynamischen Situation beschäftigt, bei der Objekte sukzessive eingefügt und entfernt werden können; die jeweils erforderlichen Änderungen des Diagramms sollen möglichst schnell ausgeführt werden. In der vorliegenden Dissertation wird eine andere, ebensowichtige Art der Dynamisierung untersucht: die Objektmenge ist fest, aber die Objekte bewegen sich auf stetigen Bahnen in der Ebene. Es soll das jeweils aktuelle Voronoi-Diagramm aufrechterhalten werden. Im ersten Kapitel seiner Arbeit gibt der Verf. zunächst eine sehr ausführliche Übersicht über das statische Voronoi-Diagramm, seine geometrischen Anwendungen, über die bekannten effizienten Algorithmen zu seiner Konstruktion und die bisher untersuchten Varianten im statischen Fall. Im zweiten Kapitel wird das ``dynamische Voronoi-Diagramm von \(n\) Punkten untersucht, die sich auf stetigen Bahnen kollisionsfrei in der Ebene bewegen. Der Autor zeigt, daß eine solche Bewegung lokal fast überall nur eine Deformation des aktuellen Voronoi-Diagramms bewirkt. Zu Änderungen seiner kombinatorischen Struktur (und nur auf diese kommt es an) kommst es nur dann, wenn 4 Punkte konzentrisch oder 3 Punkte kollinear sind. Für die weitere Untersuchung nimmt der Autor an, daß solche Ereignisse für jedes Quadrupel bzw. Tripel von Punkten höchstens \(s\) mal vorkommen, wobei \(s\) eine Konstante ist. Die Voraussetzung ist deutlich schächer als die bisher in der - spärlichen - Literatur zu diesem Thema verfolgten Ansätze. Sie ist insbesondere erfüllt für polynomiale Bahnen mit beschränktem Grad. Mit diesen Annahmen kann der Autor jedes mit Strukturänderung verbundene Ereignis in worst-case Zeit \(O(\log n)\) bearbeiten. Es wird gezeigt, daß diese Schranke erreicht werden kann, selbst wenn sich nur ein Punkt geradlinig bewegt und die übrigen fest bleiben. Zusammen mit der Berechnung des Voronoi-Diagramms der Anfangskonfiguration in Zeit \(O(n\log n)\) und dem linearen Speicherplatzbedarf ist dies der erste bekannte optimale Algorithmus zur Lösung des gestellten Problems. Es stellt sich die Frage, wieviele topologische Ereignisse auftreten können. Eine naive Abschätzung ergibt \(O(n^ 4)\). Mit Hilfe eines eleganten Abzählarguments gelingt es, \(O(n^ 2\lambda_ s(n))\) als nichttriviale obere Schranke nachzuweisen; hierbei bedeutet \(\lambda_ s(n)\) die maximale Länge einer Davenport-Schinzel-Sequenz der Ordnung \(s\) aus \(n\) Symbolen. Auch dieses Ergebnis, das vom Autor in Zusammenarbeit mit \textit{J. S. B. Mitchell} und \textit{L. Guibas} erzielt wurde, verbessert die bisher bekannten Resultate. Ob die neue Schranke dicht ist, stellt ein reizvolles Problem für die weitere Forschung dar. Im dritten Kapitel wird der vorgestellte Ansatz auf zwei Arten verallgemeinert: Anstelle von Punkten werden \(n\) konvexe Polygone betrachtet, die kollisionsfrei längs stetiger Bahnen verschoben werden dürfen, und für diese werden die Voronoi-Diagramme aller Ordnungen \(k,1\leq k\leq n-1\), gleichzeitig aufrechterhalten. Die Eigenschaften statischer Voronoi-Diagramme konvexer Polygone waren vom Autor bereits in seiner Diplomarbeit untersucht worden. Im Gegensatz zum Fall punktförmiger Objekte können sich hier die Bisektoren von drei Polygonen in zwei Punkten (statt in einem) schneiden. Für \(n\) bewegte konvexe Polygone lassen sich alle Diagramme \(k\)-ter Ordnung, \(1\leq k\leq n-1\), in optimaler Zeit \(O(\log n)\) pro Ereignis unterhalten. Hierzu wird \(O(n^ 3)\) Speicherplatz benötigt und \(O(n^ 4)\) Vorbereitungszeit für die Berechnung der Anfangsdiagramme. Nur von der letzten Schranke ist nicht bekannt, ob sie dicht ist. Daß für die Strukturänderungen nur logarithmische Zeit benötigt wird, liegt daran, daß jede Änderung höchstens 3 konsekutive Ordnungen involviert. Die maximale Anzahl von Ereignissen bei gleichzeitiger Verwaltung aller \(k\)-Voronoi-Diagramme ist durch \(O(n^ 4)\) beschränkt; diese Schranke wird bereits für Punkte angenommen. Im vierten Kapitel werden schließlich einige klassische geometrische Probleme (wie etwa die Konstruktion der konvexen Hülle oder eines minimalen spannenden Baumes) unter dynamischen Gesichtspunkten betrachtet, deren Lösungen im statischen Fall in linearer Zeit aus dem Voronoi-Diagramm abgeleitet werden können. Hierbei tritt folgendes Problem auf: Nicht jedes für das Voronoi-Diagramm wichtige Ereignis ist auch für das abgeleitete Problem relevant; hier gibt der Autor zum Teil echt kleinere Schranken an und schlägt vor, nur die relevanten Ereignisse zu bearbeiten.

Recommendations

Cited in

(21)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4023786)