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.