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
Overview
Syllabus
Assignments
Section Info
Exam Registration
Forums
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/5f738848-ea9e-423f-a70c-3a9744b89810/
Help
Opens in a new window
Syllabus
Expand All
Collapse All
Print View
1. Vorlesung, Dienstag
Tue Apr 09, 2019 02:15 PM - | 03:45 PM
Überblick, Anwendungen
Punkte, Strecken, Geraden, Ebenen, Halbebenen, Koordinaten
Polygone, Streckenzüge. einfache Polygone (bzw. Polygonränder), polygonale Gebiete
konvexe Mengen
konvexe Hülle einer Punktmenge,
O
(
n
3
) Zeit
Orientierungstest mittels Determinanten
2. Vorlesung, Donnerstag
Thu Apr 11, 2019 02:15 PM - | 03:45 PM
Orientierungstest mittels Determinanten, orientierter Flächeninhalt
Jarvis March:
O
(
n
h
), und Graham Scan:
O
(
n
)+Sortieren
Robustheit
der
optimale ausgabeabhängige Algorithmus
von Timothy Chan (1996),
O
(
n
log
h
).
Annahme: Die Anzahl
h
der Ecken auf der konvexen Hülle ist bekannt.
3. Vorlesung, Dienstag (teilweise als Übung)
Tue Apr 16, 2019 02:15 PM - | 03:45 PM
Streckenschnitt in
O
(
n
+
k
log
k
) Zeit und
O
(
n
) Speicher.
Überstreichen der Ebene durch eine Fegegerade
4. Vorlesung, Donnerstag
Thu Apr 18, 2019 02:15 PM - | 03:45 PM
Das dichteste Punktpaar, Berechnung durch Überstreichen.
Die doppelt-verkettete Kantenliste (doubly-connected edge list, DCEL) zur Darstellung ebener Unterteilungen.
5. Vorlesung, Dienstag
Tue Apr 23, 2019 02:15 PM - | 03:45 PM
Trapezzerlegung und Triangulierung eines einfachen Polygons oder einer ebenen Zerlegung
Triangulierung einer Punktmenge
Existenz und kombinatorische Eigenschaften
Dualgraph, Baumstruktur
Triangulierung einer Punktmenge als Nebenprodukt beim Graham-Scan
Konstruktion der Trapezzerlegung durch Überstreichen
Simulation von allgemeiner Lage durch symbolisches Perturbieren
6. Vorlesung, Donnerstag
Thu Apr 25, 2019 02:15 PM - | 03:45 PM
Konstruktion einer Triangulierung aus einer Trapezzerlegung
Ohren einer Triangulierung
Bewachen einer Bildergalerie
kürzester Weg in einem einfachen Polygon, Trichteralgorithmus
7. Vorlesung, Dienstag
Tue Apr 30, 2019 02:15 PM - | 03:45 PM
Orthogonale Bereichsabfragen
Bereichsbäume (range trees)
Fraktionales Kaskadieren
8. Vorlesung, Donnerstag
Thu May 02, 2019 02:15 PM - | 03:45 PM
Systematische Elimination von gleichen Werten durch lexikographische Ordnung
kd-Bäume
Nachtrag zur zweiten Vorlesung: der optimale ausgabeabhängige Algorithmus von Timothy Chan (1996),
O
(
n
log
h
), wenn die Anzahl
h
der Ecken auf der konvexen Hülle nicht bekannt ist.
9. Vorlesung, Dienstag
Tue May 07, 2019 02:15 PM - | 03:45 PM
Teile und Herrsche: dichtestes Punktpaar in der Ebene
Teile und Herrsche in hohen Dimensionen
dichtestes Punktpaar alle nahen Punktpaare bei beschränkter Dichte (Bentley und Shamos, 1978)
Ausarbeitung der Analyse
auf englisch
10. Vorlesung, Donnerstag
Thu May 09, 2019 02:15 PM - | 03:45 PM
Größtes enthaltenes Dreieck in einem konvexen Polygon,
Ausarbeitung
auf englisch,
erweiterte Ausarbeitung
kleinstes umschließendes Dreieck
11. Vorlesung, Dienstag
Tue May 14, 2019 02:15 PM - | 03:45 PM
Fertigung mit Gussformen
Schnitt von Halbebenen und Schnitt von konvexen Regionen
Lineare Optimierung in niedrigen Dimensionen durch iteratives Einfügen in zufälliger Reihenfolge
12. Vorlesung, Donnerstag
Thu May 16, 2019 02:15 PM - | 03:45 PM
Lineare Optimierung in niedrigen Dimensionen durch iteratives Einfügen in zufälliger Reihenfolge (Fortsetzung)
Rückwärtsanalyse
Test auf Unbeschränktheit
13. Vorlesung, Dienstag
Tue May 21, 2019 02:15 PM - | 03:45 PM
Kleinster einschließender Kreis
Prune and Search
Schnitt zweier konvexer Polygone
Lineare Optimierung in niedrigen Dimensionen (deterministisch)
14. Vorlesung, Donnerstag
Thu May 23, 2019 02:15 PM - | 03:45 PM
Voronoidiagramme, Definition und Eigenschaften
Konstruktion in der Ebene mit Überstreichen (nach dem Algorithmus von Steven Fortune, 1987)
15. Vorlesung, Dienstag
Tue May 28, 2019 02:15 PM - | 03:45 PM
Punktlokalisierung in einer ebenen Unterteilung
Trapezzerlegung mit randomisiserter inkrementeller Konstruktion
16. Vorlesung, Dienstag
Tue Jun 04, 2019 02:15 PM - | 03:45 PM
Nachtrag: Analyse zur Konstruktion der Trapezzerlegung
Voronoi-Diagramme 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
Umkreistest
17. Vorlesung, Donnerstag
Thu Jun 06, 2019 02:15 PM - | 03:45 PM
Triangulierungen zur Interpolation verstreuter Daten
Die Delaunay-Triangulierung
lokale Delaunay-Bedingung
Berechnung durch Kantenkippen
Maximierung des kleinsten Winkels bei der Delaunay-Triangulierung
18. Vorlesung, Dienstag
Tue Jun 11, 2019 02:15 PM - | 03:45 PM
Dreidimensionale konvexe Hülle durch zufällige Einfügereihenfolge (randomisierte inkrementelle Konstruktion, RIC)
Ausarbeitung der Analyse (
pdf
)
19. Vorlesung, Donnerstag
Thu Jun 13, 2019 02:15 PM - | 03:45 PM
Punktlokalisierung in der Ebene mit der Kirkpatrick-Hierarchie
Die Dobkin-Kirkpatrick-Hierarchie für ebene Polygonanfragen und dreidimensionale Polytopanfragen.
20. Vorlesung, Dienstag
Tue Jun 18, 2019 02:15 PM - | 03:45 PM
Bewegungsplanung für Roboter
Minkowskisumme
21. Vorlesung, Donnerstag
Thu Jun 20, 2019 02:15 PM - | 03:45 PM
Trapezzerlegung eines einfachen Polygons in
O
(
n
log
*
n
) erwarteter Zeit (
Seidel 1991
),
Ausarbeitung
Größtes enthaltenes Viereck in einem konvexen Polygon, kleinstes umgeschriebenes Parallelogramm (siehe
Artikel
zu diesem Thema)
22. Vorlesung, Dienstag
Tue Jun 25, 2019 02:15 PM - | 03:45 PM
Fortsetzung Bewegungsplanung und Minkowskisumme
Intervallbäume
23. Vorlesung, Donnerstag
Thu Jun 27, 2019 02:15 PM - | 03:45 PM
Segmentbäume
Fensteranfragen für achsenparallele / beliebig orientierte Strecken
24. Vorlesung, Dienstag
Tue Jul 02, 2019 02:15 PM - | 03:45 PM
Geometrische Optimierungsprobleme
Ansatz von
Timothy Chan (1999)
mit Hilfe einer Methode für das Entscheidungsproblem und rekursiver Zerlegung
Entscheidungsproblem für dichtestes Punktpaar mit Hashing
Überblick über den randomizierten Linearzeitalgorithmus von Michael Rabin (1976)
Das kleinste Quadrat um
k
Punkte
25. Vorlesung, Donnerstag
Thu Jul 04, 2019 02:15 PM - | 03:45 PM
geometrische Mustererkennung
gerichteter und ungerichteter Hausdorff-Abstand
Minimierung des
Hausdorff-Abstandes unter Translationen
, Lösung des Entscheidungsproblems
26. Vorlesung, Dienstag
Tue Jul 09, 2019 02:15 PM - | 03:45 PM
Hausdorffabstand zwischen Streckenmengen, (
H. Alt, B. Behrends, J. Blömer
, 1995)
Quadbäume, ausgeglichene Quadbäume
27. Vorlesung, Donnerstag
Thu Jul 11, 2019 02:15 PM - | 03:45 PM
Quadbäume und Gittererzeugung
Diskrepanz von Punktmengen bezüglich einer Menge von Bereichen
Konstruktion von Geradenarrangements
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.