Geometria obliczeniowa 2017

Wtorek 13¹⁵ - 15⁰⁰ C-13/0.38 wykład

Wtorek 15¹⁵ - 16⁵⁵ D-1/312B ćwiczenia

Literatura

1. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Geometria obliczeniowa: algorytmy i zastosowania, WNT, Warszawa 2007 (ISBN 978-83-204-3244-2)
2. F.P. Preparata, M.I. Shamos, Geometria obliczeniowa. Wprowadzenie, Helion, 2003 (ISBN 83-7361-098-7)
3. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa 1997 (ISBN 83-204-2144-6)

Tematy wykładów (w przybliżeniu)

1. Wprowadzenie. (28-02-2017)
   [Podstawowe pojęcia; szukanie przecięć w zbiorze odcinków.]
2. Triangulacja wielokątów. (7-03-2017)
   [Problem galerii i strażników; triangulacja przekątnymi wielokątów wypukłych; triangulacja przekątnymi wielokątów monotonicznych;]
3. Triangulacja wielokątów. (14-03-2017)
   [Triangulacja przekątnymi wielokątów prostych; podział na trapezy; podział na wielokąty monotoniczne; podział na wielokąty wypukłe.]
4. Przecięcia. (21-03-2017)
   [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.]
5. Przeszukiwanie obszarów. (28-03-2017)
   [Kd-drzewa; drzewa obszarów.]
6. Lokalizacja punktu. (4-04-2017)
   [Sprawdzenie czy punkt jest wewnątrz wielokąta; podział płaszczyzny na pasy; mapy trapezoidów.]
7. Otoczki Wypukłe. (11-04-2017)
   [Algorytmy Grahama, Jarvisa i „dziel i rządź”; granica dolna.]
8. Diagramy Voronoi. (25-04-2017)
   [Własności diagramów Voronoi; algorytmy wyznaczania diagramów Voronoi: „dziel i rządź” oraz z prostą zamiatającą.]
9. Triangulacja Delaunay-a (9-05-2017)
   [Podstawowe własności triangulacji Delaunay-a; związek z diagramami Voronoi; minimalne euklidesowe drzewo rozpinające; para najdalszych punktów w zbiorze.]
10. Przemieszczanie obiektów. Grafy widzialności. (16-05-2017)
    [Robot punktowy; obliczanie grafu widzialności; najkrótsza ścieżka dla robota.]
11. Przemieszczanie obiektów. (cd) (23-05-2017)
    [Sumy Minkowskiego.]
12. Dualizacja liniowa i problemy z nią związane. (30-05-2017)
    [Dualizacja liniowa; sortowanie biegunowe n punktów; prosta przecinająca n odcinków; problem wyważania.]
13. Dualizacja liniowa ... (cd) (6-06-2017)
    [Problem mediany zbioru; problem „kanapki z szynką”.]
14. Algorytmy równoległe w geometrii obliczeniowej. (13-06-2017)
15. Kolokwium zaliczeniowe. (20-06-2017)

Ćwiczenia

Lista zadań

Przydział zadań

1. Zad. 1-4 (28-02-2017)
2. Zad. 5-8 (7-03-2017)
3. Zad. 9-12 (14-03-2017)
4. Godziny dziekańskie (zamiana z wykładem)
5. Zad. 13-16 (28-03-2017)
6. Zad. 17-19 (4-04-2017)
7. Zad. 20-23 (11-04-2017)
8. Zad. 24-27 (25-04-2017)
9. Zad. 28-30 (9-05-2017)
10. Zad. 31-32 (16-05-2017)
11. Zad. 33-35 (23-05-2017)
12. Zad. 36-38 (30-05-2017)
13. Zad. 39-44 (6-06-2017)
14. Zad. 45-49 (13-06-2017)

Zasady zaliczenia kursu

Kurs będzie zaliczany na podstawie kolokwium końcowego które odbędzie się na ostatnim wykładzie. 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. Oddanie zadań na następnych ćwiczeniach (pierwszych po tych na których zadanie zostało wykonane przy tablicy) jest traktowane jako aktywność.