Algorithmische Geometrie

Wie bestimmt man in einer Menge von Punkten am schnellsten zu jedem Punkt seinenn] achstenNachbarn?Wiel] a tsichderDurchschnittvonzweiPolygonene?zient berechnen? Wie ?ndet man ein Ziel in unbekannter Umgebung? Mit diesen und vielen anderen Fragen befa t sich die Algorithmische Geometrie, ein Teilgebiet der Informatik, dessen Entwicklung vor rund zwanzig Jahren begann und seitdem einen stur ] mischen Verlauf genommen hat. Aus gutem Grund: Zum einen ist die Beschaftigung mit geometrischen Problemen selbst sehr reizvoll. Oft gilt es, ] verborgene strukturelle Eigenschaften aufzudecken, bevor ein e?zienter Algorithmus entwickelt werden kann. Zum anderen haben die untersuchten Fragen einen direkten Bezug zu realenProblemenin Anwendungsgebietenwie Computergraphik, Comput- vision, Geographische Informationssysteme oder Robotik. Dieses Buch gibt eine Einfuhrung in die Algorithmische Geometrie und demon- ] striert hau?g verwendete Techniken an ausgesuchten Beispielen. Es wendet sich an ] Studierende, die uber elementare algorithmische Grundkenntnisse verfugen, und an ] ] alle, die beruflich mit geometrischen Fragen zu tun haben oder sich fur dieses Gebiet ] interessieren. Die Grundlage bildet ein Kurs der FernUniversitat Hagen im Umfang ] einer Hauptstudiumvorlesung von vier Semesterwochenstunden; das Buch ist deshalb fur ] ein Selbststudium konzipiert.