Geometria obliczeniowa 2015
Środa 1115 - 1300 C-13/0.31 wykład
Środa 1315 - 1500 C-13/0.31 ćwiczenia
Literatura
- M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf,
Geometria obliczeniowa: algorytmy i zastosowania,
WNT, Warszawa 2007 (ISBN 978-83-204-3244-2)
- F.P. Preparata, M.I. Shamos,
Geometria obliczeniowa. Wprowadzenie,
Helion, 2003 (ISBN 83-7361-098-7)
- T.H. Cormen, Ch.E. Leiserson, R.L. Rivest,
Wprowadzenie do algorytmów,
WNT, Warszawa 1997 (ISBN 83-204-2144-6)
Tematy zajęć (w przybliżeniu)
- Wprowadzenie. (25-02-2015)
[Podstawowe pojęcia; szukanie przecięć w zbiorze odcinków.]
- Triangulacja wielokątów. (25-02-2015)
[Problem galerii i strażników; triangulacja przekątnymi wielokątów wypukłych; triangulacja przekątnymi wielokątów monotonicznych;]
- Triangulacja wielokątów. (4-03-2015)
[Triangulacja przekątnymi wielokątów prostych; podział na trapezy; podział na wielokąty monotoniczne; podział na wielokąty wypukłe.]
- Przecięcia. (11-03-2014)
[Część wspólna dwóch wielokątów prostych; część wspólna dwóch wielokątów wypukłych; przecięcie zbioru półpłaszczyzn; jądro wielokąta prostego.]
- Przeszukiwanie obszarów. (18-03-2015)
[Kd-drzewa; drzewa obszarów.]
- Lokalizacja punktu. (25-03-2015)
[Sprawdzenie czy punkt jest wewnątrz wielokąta; podział płaszczyzny na pasy; mapy trapezoidów.]
- Otoczki Wypukłe. (1-04-2015)
[Algorytmy Grahama, Jarvisa i „dziel i rządź”; granica dolna.]
- Diagramy Voronoi. (15-04-2015)
[Własności diagramów Voronoi; algorytmy wyznaczania diagramów Voronoi: „dziel i rządź” oraz z prostą zamiatającą.]
- Triangulacja Delaunay-a (22-04-2015)
[Podstawowe własności triangulacji Delaunay-a; związek z diagramami Voronoi; minimalne euklidesowe drzewo rozpinające; para najdalszych punktów w zbiorze.]
- Przemieszczanie obiektów. Grafy widzialności. (29-04-2015)
[Robot punktowy; obliczanie grafu widzialności; najkrótsza ścieżka dla robota.]
- Przemieszczanie obiektów. (cd) (6-05-2015)
[Sumy Minkowskiego.]
- Dualizacja liniowa i problemy z nią związane. (13-05-2015)
[Dualizacja liniowa; sortowanie biegunowe n punktów; prosta przecinająca n odcinków; problem wyważania.]
- Dualizacja liniowa ... (cd) (20-05-2015)
[Problem mediany zbioru; problem „kanapki z szynką”.]
- Algorytmy równoległe w geometrii obliczeniowej na przykłądzie otoczki wypukłej. (27-05-2015)
- Kolokwium zaliczeniowe. (17-06-2015)
Ćwiczenia
- Zad. 1-5 (4-03-2015)
- Zad. 6-11 (11-03-2015)
- Zad. 12-14 (18-03-2015)
- Zad. 15-17 (25-03-2015)
- Zad. 18-20 (1-04-2015)
- Zad. 21-24 (15-04-2015)
- Zad. 25-27 (22-04-2015)
- Zad. 28-32 (29-04-2015)
- Zad. 33-35 (6-05-2015)
- Zad. 36-40 (13-05-2015)
- Zad. 41-44 (20-05-2015)
- Zad. 45-49 (27-05-2015)
- Sprawdzanie przydzielonych zadań (10-06-2015)
- Sprawdzanie przydzielonych zadań (10-06-2015)
- Sprawdzanie przydzielonych zadań (17-06-2015)
Listy zadań
Zasady zaliczenia kursu
Kurs będzie zaliczany na podstawie kolokwium końcowego. Na kolokwium jedyną dopuszczalną pomocą naukową jest kartka formatu A4, wyraźnie podpisana. Ocena z kursu może być podwyższona w przypadku wykazania się aktywnością na ćwiczeniach lub w dziedzinach związanych z tematyką wykładu.
Dodatkowym warunkiem zaliczenia jest oddanie przez studenta w formie pisemnej (PDF) wyznaczonych zadań. Oddawane zadanie powinno być rozwiązane dokładnie, w sposób formalny i przejrzysty. Zadania wyznacza prowadzący ćwiczenia.