Click here to exit full screen mode.
Sakai works much better when JavaScript is enabled. Please enable JavaScript in your Browser.
jump to content
[c]
Sites
[w]
Tools
[l]
Syllabus
Log In
Tools list begins here
Home
Syllabus
Assignments
Section Info
Exam Registration
Forums
Commons
Polls
Help
Opens in a new window
Expand/collapse tool navigation
Algorithmische Geomet ...
Syllabus
Content begins here
Syllabus
Link
Direct link to this tool
Short URL
https://mycampus.imp.fu-berlin.de/portal/directtool/6b2671bc-9021-4cf0-a070-aeb8b69ccfd6/
Help
Opens in a new window
Syllabus
Expand All
Collapse All
Print View
1. Vorlesung Montag
Mon Apr 14, 2025 10:15 AM - | 11:45 AM
Überblick, Anwendungen
Punkte, Strecken, Geraden, Ebenen, Halbebenen, Koordinaten
Polygone, Streckenzüge. einfache Polygone (bzw. Polygonränder), polygonale Gebiete
konvexe Mengen
konvexe Hülle konv(
S
) einer Punktmenge
Charaktisierung der Hüllenkanten,
O
(
n
3
) Zeit
allgemeine Lage
Orientierungstest mittels Determinanten, orientierter Flächeninhalt
2. Vorlesung Donnerstag
Thu Apr 17, 2025 02:15 PM - | 03:45 PM
Orientierungstest mittels Determinanten, orientierter Flächeninhalt
Jarvis March:
O
(
n
h
)
Graham Scan: Sortieren+
O
(
n
)
Robustheit
Streckenschnitt in
O
(
(n
+
k
) log
n
) Zeit und
O
(
n
) Speicher.
Überstreichen der Ebene durch eine Fegegerade
3. Vorlesung Donnerstag
Thu Apr 24, 2025 02:15 PM - | 03:45 PM
Die doppelt-verkettete Kantenliste (doubly-connected edge list, DCEL) zur Darstellung einer
ebenen Unterteilung
Halbkanten, Ecken, Flächen
Inzidenz
Zeiger
twin
,
next
,
prev
äußerer Rand und innere Ränder
Durchwandern der Unterteilung
Erweiterungen, Sonderfälle: unendliche Strahlen, isolierte Knoten
Erstellen einer DCEL aus einer kreuzungsfreien Streckensuppe in O(n log n) Zeit:
zyklisches Sortieren der inzidenten Kanten um jeden Punkt
Schießen von den Extrempunkten aus mit Überstreichen
4. Vorlesung Montag
Mon Apr 28, 2025 10:15 AM - | 11:45 AM
Übereinanderlegen zweier ebener Unterteilungen mit Überstreichen in
O
(
(n
+
k
) log
n
) Zeit
Triangulierung eines einfachen Polygons oder einer ebenen Zerlegung
Triangulierung einer Punktmenge
Triangulierung einer Punktmenge als Nebenprodukt beim Graham-Scan (Übung 9)
Existenz und kombinatorische Eigenschaften
Dualgraph, Baumstruktur, Ohren einer Triangulierung
kürzester Weg in einem triangulierten einfachen Polygon in linearer Zeit
Folge von Dreiecken als Weg im Dualgraph
5. Vorlesung Montag
Mon May 05, 2025 10:15 AM - | 11:45 AM
kürzester Weg in einem triangulierten einfachen Polygon in linearer Zeit, Trichteralgorithmus
Öffnung der Trichters (aktuelles Fenster), Spitze, linker Rand, rechter Rand
Trapezzerlegung einer ebenen Unterteilung
Konstruktion der Trapezzerlegung durch Überstreichen
Bewachen einer Bildergalerie (
art gallery problems
)
6. Vorlesung Montag
Mon May 12, 2025 10:15 AM - | 11:45 AM
Konstruktion einer Triangulierung aus einer Trapezzerlegung
Diagonalen in jedes Trapez einfügen
Diagonalen zwischen in
x
-Reihenfolge benachbarten Ecken am oberen und am unteren Rand
Triangulierung der entstehenden
Landschaftspolygone
Simulation von allgemeiner Lage durch symbolisches Stören (Perturbieren)
lexikographische Auflösung von Entartungen
Das dichteste Punktpaar, Berechnung durch Überstreichen
Packungsargument
7. Vorlesung Donnerstag
Thu May 15, 2025 02:15 PM - | 03:45 PM
Orthogonale Bereichsabfragen
Bereichsbäume (range trees)
kanonische Mengen
Fraktionales Kaskadieren
Anzahlabfragen und erweiterte Abfragen (Summe der Gewichte und Maximum)
8. Vorlesung Montag
Mon May 19, 2025 10:15 AM - | 11:45 AM
kd-Bäume
Punktlokalisierung in einer ebenen Unterteilung
Trapezzerlegung mit inkrementeller Konstruktion
9. Vorlesung Donnerstag
Thu May 22, 2025 02:15 PM - | 03:45 PM
Trapezzerlegung mit randomisierter inkrementeller Konstruktion
Rückwärtsanalyse
Postamtsproblem
Voronoidiagramme, Definition und Eigenschaften
10. Vorlesung Montag
Mon May 26, 2025 10:15 AM - | 11:45 AM
Konstruktion des Voronoidiagramms in der Ebene mit Überstreichen (nach dem Algorithmus von Steven Fortune, 1987)
Uferlinie, Punktereignisse, Umkreisereignisse
Jede Voronoiecke wird durch ein Umkreisereignis gefunden
Animation
,
Animation
11. Vorlesung Montag
Mon Jun 02, 2025 10:15 AM - | 11:45 AM
Das Voronodiagramm als untere Einhüllende der Abstandsfunktionen
Transformation der Abstandsfunktionen
Dualität von Punkten und Geraden in der Ebene, und von Punkten und Ebenen im Raum
Untere konvexe Hülle und obere Einhüllende von Geraden
Die Delaunay-Triangulierung als dualer Graph zum Voronoidiagramm
Das Kriterium vom leeren Kreis
12. Vorlesung Donnerstag
Thu Jun 05, 2025 02:15 PM - | 03:45 PM
Triangulierungen zur Interpolation verstreuter Daten
räumliches Modell: untere konvexe Hülle
lokale Delaunay-Bedingung und globale Delaunay-Bedingung
Berechnung der Delaunay-Triangulierung durch Kantenkippen
Maximierung des kleinsten Winkels durch die Delaunay-Triangulierung
13. Vorlesung Donnerstag
Thu Jun 12, 2025 02:15 PM - | 03:45 PM
Zwei unabhängige Wege zur räumlichen Interpretation der Delaunay-Triangulierung
Randomisierte inkrementelle Konstruktion der Delaunay-Triangulierung (Thema wurde nur angerissen)
Umkreistest mittels Determinanten
Potenz eines Punktes bezüglich einem Kreis, Potenzgerade
Navigieren in einer Triangulierung
Azyklische Eigenschaft der davor-danach-Relation von einem Punkt aus gesehen, unter Annahme allgemeiner Lage
Die lokale Delaunay-Bedingung für alle Kanten impliziert die globale Delaunay-Bedingung
Kantenkippen in höheren Dimensionen
2-3-Kippungen und 3-2-Kippungen in drei Dimensionen
14. Vorlesung Montag
Mon Jun 16, 2025 10:15 AM - | 11:45 AM
Fensteranfragen für orthogonale Strecken
Intervallbäume und Prioritätssuchbäume
15. Vorlesung Donnerstag (per Video)
Thu Jun 19, 2025 02:15 PM - | 03:45 PM
Geometrische Optimierungsprobleme und die entsprechenden Entscheidungsprobleme
Video
(27 min, 60MByte),
Folien
Entscheidungsproblem für dichtestes Punktpaar mit Hashing nach Michael Rabin (1976)
[ Ein etwas anderer Algorithmus, der auf denselbel Ideen beruht: siehe Kapitel
dichtestes Punktpaar und kleinster umschließender Kreis durch Gitterrundung
aus dem Buch
Geometric approximation algorithms
von Sariel Har-Peled ]
Ansatz von
Timothy Chan (1999)
mit Hilfe einer Methode für das Entscheidungsproblem und rekursiver Zerlegung,
Video
(22 min, 50MByte)
Inkrementeller randomisierter Linearzeitalgorithmus für das dichteste Punktpaar
Finden von Hotspots: kleinstes Quadrat mit
k
Punkten
16. Vorlesung Montag
Mon Jun 23, 2025 10:15 AM - | 11:45 AM
Fensteranfragen für beliebige nichtkreuzende Strecken
Segmentbäume
17. Vorlesung Donnerstag (per Video)
Thu Jun 26, 2025 10:15 AM - | 11:45 AM
der
optimale ausgabeabhängige Algorithmus
zur Berechung der konvexen Hülle von Timothy Chan (1996),
O
(
n
log
h
)
Video
(27 min, 57MByte),
Folien
Trapezzerlegung eines einfachen Polygons in
O
(
n
log
*
n
) erwarteter Zeit (
Seidel 1991
)
Video
(20 min, 75MByte),
Folien
[ Ältere
Ausarbeitung
eines leicht abgeänderten Ansatzes mit etwas geänderter Notation. Insbesondere haben
n
1
und
n
2
eine andere Bedeutung als in der Vorlesung. ]
18. Vorlesung Montag
Mon Jun 30, 2025 10:15 AM - | 11:45 AM
Quadbäume
ausgeglichene Quadbäume: Definition
gute Gitter aus Quadbäumen:
Beispiel
,
Beispiel 2
, Seite 2 der
Folien
Bewegungsplanung für Roboter
Arbeitsraum, Konfigurationsraum, freier und verbotener Raum
Video
zur Veranschaulichung des Konfigurationsraum für einen drehbaren Roboter
Bewegungsplanung für Roboter unter Translationen
Minkowski-Summe
19. Vorlesung Donnerstag
Thu Jul 03, 2025 10:15 AM - | 03:45 PM
Balancierte Quadbäume
Korrektur der Definition: Das Größenverhältnis zwischen benachbarten Quadraten ist höchstens 2.
Konstruktionsalgorithmus in linearer Zeit (
Ausarbeitung
, auf englisch)
Analyse der Größe
Minkowskisumme
Zwei konvexe Polygone. Extreme Punkte. Linearzeitalgorithmus
(
m
n
)
2
Komplexität für zwei nichtkonvexe Polygone
2025-07-03-make-quadtree-balanced.pdf
20. Vorlesung Montag
Mon Jul 07, 2025 10:15 AM - | 11:45 AM
Minkowskisumme
Berechnung der Minkowski-Summe von nichtkonvexen Polygonen
Pseudokreise und ihre Vereinigung
Bestimmen des verbotenen Konfigurationsraumes mit teile-und-herrsche
Trapezzerlegung des freien Raumes zur Navigation im freien Raum
Kürzester Weg in einem Polygon mit Hindernissen mit dem Sichtbarkeitsgraphen (nur erwähnt)
21. Vorlesung Donnerstag
Thu Jul 10, 2025 02:15 PM - | 03:00 PM
Lineare Programmierung in 2 und 3 Dimensionen
Fertigung mit Gussformen
deterministischer Algorithmus: prune-and-search (in 2 Dimensionen)
22. Vorlesung Montag
Mon Jul 14, 2025 10:15 AM - | 11:45 AM
Lineare Programmierung in
d
Dimensionen
randomisierter Algorithmus: Rückwärtsanalyse
Konvexe Hülle in 3D mit "giftwrapping"
23. Vorlesung Donnerstag
Thu Jul 17, 2025 02:15 PM - | 03:45 PM
Dobkin-Kirkpatrick-Hierarchie für ein dreidimensionales Polytop
Geometrische Mustererkennung
Hausdorffabstand zwischen Streckenmengen, (
H. Alt, B. Behrends, J. Blömer
, 1995)
Klausur Donnerstag
Thu Jul 24, 2025 02:10 PM - | 03:45 PM
Are you sure you want to delete
Title
Content
Click to add title
Start Date
End Date
Click to add start date
Click to add end date
Click to add body text
Saved
Deleted
An error occurred while saving. Refresh the page and try again.
This field is required.
Start date must be before end date.
Please select a start or end date before posting to the calendar.
Click to expand/collapse, change attachments or edit body content.
Delete
Cancel
Are you sure you want to delete
Delete Item
Delete Attachment
Add
Add and Publish
Add Item
DRAFT -
WARNING: this action cannot be undone.