Algorithmen in einer Kurzfassung, 2.

Kapitel 9. Computergestützte Geometrie

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

Computergeometrie ist die rigorose Anwendung der Mathematik, um geometrische Strukturen und ihre Eigenschaften genau und effizient zu berechnen. Wir beschränken uns auf die Lösung von Problemen mit zweidimensionalen Strukturen, die in der kartesischen Ebene dargestellt werden; es gibt natürliche Erweiterungen auf n-dimensionale Strukturen. Mathematikerinnen und Mathematiker beschäftigen sich schon seit Jahrhunderten mit solchen Problemen, aber erst seit den 1970er Jahren ist das Gebiet als systematische Studie anerkannt. In diesem Kapitel werden die rechnerischen Abstraktionen vorgestellt, die zur Lösung rechnerischer Geometrieprobleme verwendet werden. Diese Techniken sind keineswegs auf Geometrieprobleme beschränkt und haben viele reale Anwendungen.

Algorithmen in dieser Kategorie lösen zahlreiche Probleme aus der realen Welt:

Konvexe Hülle

Berechne die kleinste konvexe Form, die eine Menge von n zweidimensionalen Punkten, P, vollständig umschließt. Dies kann in O(n log n) gelöst werden, anstatt einer O(ⁿ⁴) Brute-Force-Lösung.

Sich schneidende Liniensegmente

Berechne alle Schnittpunkte für eine Menge von n zweidimensionalen Liniensegmenten S. Diese Aufgabe kann in O((n + k) log n) gelöst werden, wobei k die Anzahl der Schnittpunkte ist, anstelle einer O(ⁿ²) Brute-Force-Lösung.

Voronoi-Diagramm

Unterteile ...