Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


24. Elementare geometrische Methoden



Computer werden in steigendem Maße zur Lösung von umfangreichen Problemen geometrischer Natur eingesetzt. Geometrische Objekte wie Punkte, Linien und Polygone sind die Grundlage für ein breites Spektrum wichtiger Anwendungen und führen zu einer interessanten Gruppe von Problemen und Algorithmen.

Geometrische Algorithmen sind für die Entwicklung und Analyse von Systemen von Bedeutung, mit denen physikalische Objekte modelliert werden, von Gebäuden und Autos bis hin zu VLSI-Schaltungen. Ein Konstrukteur, der mit einem physikalischen Objekt arbeitet, hat eine geometrische Intuition, die sich schwer auf eine computerisierte Darstellung übertragen läßt. Viele andere Anwendungen erfordern unmittelbar die Verarbeitung geometrischer Daten. Zum Beispiel ist ein politisches »Wahlbetrugs«-Schema zur Aufteilung eines Regierungsbezirks in Wahlkreise mit gleicher Bevölkerungszahl (in der Weise, daß noch andere Kriterien erfüllt sind, wie etwa, daß die meisten Mitglieder der anderen Partei auf einem Gebiet konzentriert werden) ein komplizierter geometrischer Algorithmus. Weitere Anwendungen sind in großer Zahl in der Mathematik und in der Statistik zu finden, Gebieten, in denen viele Probleme in natürlicher Weise zu einer geometrischen Darstellung führen.

Bei der Mehrzahl der Algorithmen, die wir betrachtet haben, wurden Text und Zahlen verwendet, die in den meisten Programmiersystemen auf natürliche Art dargestellt und verarbeitet werden. Tatsächlich sind die benötigten elementaren Operationen in den meisten Computersystemen hardwaremäßig implementiert. Wir werden sehen, daß die Situation bei geometrischen Problemen anders ist: Selbst die einfachsten Operationen mit Punkten und Linien können mittels Computer schwer realisierbar sein.

Geometrische Probleme lassen sich leicht veranschaulichen, doch das kann störend sein. Viele Probleme, die jemand sofort lösen kann, der ein Stück Papier betrachtet (Beispiel: Befindet sich ein gegebener Punkt innerhalb eines gegebenen Polygons?), erfordern nichttriviale Programme. Für kompliziertere Probleme kann sich (wie bei vielen anderen Anwendungen) das für eine Implementation geeignete Lösungsverfahren durchaus stark von der für einen Menschen geeigneten Lösungsmethode unterscheiden.

Aufgrund der konstruktiven Natur der antiken Geometrie und weiten Verbreitung nützlicher Anwendungen könnte man annehmen, daß geometrische Algorithmen auf eine lange Geschichte zurückblicken können; in Wirklichkeit ist ein großer Teil der Arbeit auf diesem Gebiet erst in jüngster Vergangenheit geleistet worden. Trotzdem ist die Arbeit von Mathematikern der Antike oft von Nutzen für die Entwicklung von Algorithmen für moderne Computer. Die Untersuchung der geometrischen Algorithmen ist deshalb interessant, weil ein starker historischer Zusammenhang vorliegt, weil immer noch neue grundlegende Algorithmen entwickelt werden und weil viele wichtige umfangreiche Anwendungen diese Algorithmen erfordern.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]