*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 12
Dienstag, 19.09.2000, 15.00–15.20 Uhr, WIL A 124

Probleme und Ergebnisse für Parallele Algorithmen zur Sichtbarkeit

Hans-Dietrich Hecker, Friedrich-Schiller-Universität Jena

Auf eine Fragestellung von V. Klee geht das bekannte Art Gallery Problem zurück. Spätestens seit dem bekannten Buch von J.°O. Rourke über dieses Thema ist die entsprechende Theorie dazu fester Bestandteil von Untersuchungen zur Sichtbarkeit geworden. Wie auch bei geometrisch orientierten Arbeiten wurden die Untersuchungen zu algorithmischen Problemen in diesem Zusammenhang von klassischen Sichtbarkeiten auf andere Ansätze erweitert, wie zum Beispiel auf die Rechtecksichtbarkeit. Eine Fülle von Arbeiten über serielle Algorithmen entstand, bei Problemen von Polygonen mit Löchern muss in den meisten Fällen damit gerechnet werden, dass die Probleme NP-schwer sind. NP-schwer sind aber auch einige Minimalprobleme für einfache Polygone, selbst die Einschränkung auf orthogonale Polygone ändert daran nichts. Wir haben uns u. a. mit Horizontalwächtermengen beschäftigt, dort gibt es entsprechende effiziente serielle Algorithmen. Es geht um die Berechnung einer minimalen Horizontalwächtermenge für Ortho-Polygone. Die seriellen bekannten Algorithmen sind vom Ansatz her Gleitgeradenmethoden bzw. verfolgen Strategien, die alles andere als natürlich parallelisiert werden können. Hinzu kommt die Forderung nach Optimalität der Algorithmen, in unserem Fall bedeutet das lineare Kosten. Damit entfällt eine Gleitgeradenmethode wegen des zu hohen Sortieraufwandes. Eine neue Variante der Baumkontraktion aus der Theorie Paralleler Algortihmen, die für dieses geometrische Problem eingesetzt wurde, ermöglicht im Zusammenwirken mit Standardtechniken einen schnellen parallelen Algorithmus in quadratisch logarithmischer Zeit mit linearen Kosten. Wir sind überzeugt davon, daß die entwickelte Technik auch für ähnliche Probleme eingesetzt werden kann. In dem Vortrag wird versucht, die notwendigen Begriffe, die zum Verständnis aus dem Gebiet der Parallelen Algorithmen notwendig sind, bereit zu stellen.