Diplomarbeit – Algorithmen zur Bestimmung konvexer Hüllen
Diese Seite gibt einen Überblick über meine Diplomarbeit, die sich mit Algorithmen zur Bestimmung konvexer Hüllen beschäftigt. Die Arbeit entstand im Jahr 1995 an der Universität Bayreuth im Fachbereich Mathematik und Physik und wurde von Frank Lempio betreut.
Die Arbeit verbindet mathematische Grundlagen mit algorithmischen Ansätzen und praktischer Umsetzung. Die vollständige Diplomarbeit steht zusätzlich als PDF zur Verfügung.
Thema und Hintergrund
Im Mittelpunkt der Arbeit steht die Frage, wie sich die konvexe Hülle einer endlichen Punktmenge effizient bestimmen lässt. Dieses Problem spielt in verschiedenen Bereichen eine Rolle, unter anderem in der Computergrafik, Mustererkennung und Bildverarbeitung.
Ziel der Arbeit war es, bestehende Algorithmen zu analysieren, ihre Eigenschaften zu vergleichen und deren Einsatzmöglichkeiten zu untersuchen.
Inhalte der Arbeit
Die Diplomarbeit gliedert sich in mehrere Abschnitte:
- Einführung in mathematische Grundlagen wie konvexe und affine Hüllen
- Vorstellung und Vergleich verschiedener Algorithmen zur Bestimmung konvexer Hüllen
- Analyse von Laufzeit und Effizienz der Verfahren
- Implementierung eines ausgewählten Algorithmus
- Anwendung der Verfahren auf praktische Problemstellungen
Im Rahmen der Arbeit wurden mehrere klassische Verfahren analysiert, verglichen und teilweise implementiert. Dazu zählen unter anderem:
- Verfahren nach Ronald Graham
- Algorithmen von Chand and Kapur
- Verfahren von Michael Kallay
- Ansätze von Mark Overmars und Jan van Leeuwen
- Verfahren von Selim Akl
Diese Algorithmen unterscheiden sich hinsichtlich ihrer Laufzeit, Struktur und praktischen Anwendbarkeit und werden im Rahmen der Arbeit systematisch gegenübergestellt.
Ergebnisse und Erkenntnisse
Die Arbeit zeigt, dass für das Problem der konvexen Hülle in der Ebene effiziente Algorithmen mit optimaler Laufzeit existieren. Insbesondere können Verfahren mit einer Laufzeit von O(n log n) das Problem effizient lösen.
Ein weiterer Aspekt ist die praktische Umsetzung eines Algorithmus und die Untersuchung seines Laufzeitverhaltens anhand konkreter Beispiele.
Einordnung
Die Diplomarbeit verbindet theoretische Mathematik mit algorithmischer Umsetzung und zeigt, wie sich abstrakte Konzepte in konkrete Verfahren übertragen lassen.
Auch heute bildet das Thema konvexer Hüllen eine Grundlage für viele Anwendungen in Informatik und Datenverarbeitung.
Rahmendaten
- Universität: Universität Bayreuth
- Fachbereich: Mathematik und Physik
- Betreuer: Frank Lempio
- Jahr: 1995