Geometria obliczeniowa 2020

Czwartek 7³⁰ - 9⁰⁰ C-13/1.27 wykład

Środa 11¹⁵ - 13⁰⁰ C-7/202 ć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)
   (Wersja angielska)
2. F.P. Preparata, M.I. Shamos, Geometria obliczeniowa. Wprowadzenie, Helion, 2003 (ISBN 83-7361-098-7)
   (Wersja angielska)
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. (26-02-2020)
   [Podstawowe pojęcia.]
2. Triangulacja wielokątów. (27-02-2020) [1,rozdział 3] [2,rozdział 6.2]
   [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. (5-03-2020) [1,rozdział 3] [2,rozdział 6.2]
   [Podział na wielokąty monotoniczne, podział na wielokąty wypukłe. Przecięcia odcinków.]
4. Przecięcia. (12-03-2018) [1,rozdział 4]
   [Część wspólna dwóch wielokątów prostych, część wspólna dwóch wielokątów wypukłych. Programowanie liniowe i przecięcie zbioru półpłaszczyzn. Jądro wielokąta prostego.]
5. Przeszukiwanie obszarów. (17-03-2020) [1,rozdział 5] [2,rozdział 2.3]
   [Kd-drzewa, drzewa obszarów.]
6. Lokalizacja punktu. (24-03-2020) [1,rozdział 6] [2,rozdział 2.2]
   [Sprawdzenie czy punkt jest wewnątrz wielokąta; podział płaszczyzny na pasy; mapy trapezoidów.]
7. Otoczki Wypukłe. (2-04-2020) [1,rozdział 11] [2,rozdział 3]
   [Algorytmy Grahama, Jarvisa i „dziel i rządź”; granica dolna.]
8. Diagramy Voronoi. (16-04-2020) [1,rozdział 7] [2,rozdział 5.5]
   [Własności diagramów Voronoi; algorytmy wyznaczania diagramów Voronoi: „dziel i rządź” oraz z prostą zamiatającą.]
9. Triangulacja Delaunay-a (23-04-2020) [1,rozdział 9] [2,rozdział 5.6 i 6.1]
   [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. (30-04-2020) [1,rozdział 13 i 15]
    [Robot punktowy; obliczanie grafu widzialności; najkrótsza ścieżka dla robota.]
11. Przemieszczanie obiektów. (cd) (7-05-2020) [1,rozdział 13]
    [Sumy Minkowskiego. Robot niepunktowy.]
12. Dualizacja liniowa i problemy z nią związane. (14-05-2020) [Szkic notatek]
    [Dualizacja liniowa; prosta przecinająca n odcinków; problem wyważania.]
13. Dualizacja liniowa ... (cd) (21-05-2020) [Szkic notatek]
    [Problem mediany zbioru; problem „kanapki z szynką”.]
14. Algorytmy równoległe w geometrii obliczeniowej. (28-05-2020) [3,rozdział 30]
15. Kolokwium zaliczeniowe. (4-06-2020)

Ćwiczenia

Lista zadań

Przysłane zadania (numer zadania/liczba przysłanych, stan na dany dzień):
2020-05-25:
2020-05-22:
2020-05-29:
2020-06-01:
2020-06-03:
2020-06-04:
2020-06-08:

1. Zad. 1-5 (4-03-2020)
2. Zad. 6-9 (11-03-2020)
3. Zad. 10-12 (18-03-2020)
4. Zad. 13-16 (25-03-2020)
5. Zad. 17-19 (1-04-2020)
6. Zad. 20-23 (8-04-2020)
7. Zad. 24-27 (15-04-2020)
8. Zad. 28-30 (22-04-2020)
9. Zad. 31-32 (29-04-2020)
10. Zad. 33-35 (6-05-2020)
11. Zad. 36-40 (13-05-2020)
12. Zad. 41-44 (20-05-2020)
13. Zad. 45-49 (27-05-2020)
14. Poprawianie rozwiązań zadań (3-06-2020)
15. Poprawianie rozwiązań zadań (10-06-2020)

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ść.

Alternatywne zasady zaliczenia kursu

1. Przedmiot można zaliczyć przesyłając rozwiązania podanych w następnym punkcie zadań z listy. Rozwiązanie każdego zadania powinno być w osobnym pdf-ie. Rozwiązania wymagające według prowadzącego poprawek powinny być poprawione w ciągu tygodnia.
2. Zadania są punktowane następująco:
   1 pkt: zadania 7, 8, 9, 10, 11, 14, 15, 16, 20, 21, 22, 23, 24, 28, 29, 30, 33, 34, 36, 37, 41, 42;
   2 pkt: zadania 6, 12, 13, 25, 26, 32, 38, 40, 43, 44.
3. Punkty są przyznawane następująco: jeśli dane zadanie przyśle co najwyżej 5 osób - wszystkie dostają całość punktów za zadanie; jeśli przyśle 6 do 10 osób - wszystkie dostają połowę punktów za zadanie; 11-20 osób - jedna czwarta punktów; powyżej 20 osób - jedna ósma punktów.
4. Ocena końcowa: liczba punktów za zadania zaokrąglona do najbliższej oceny (w przypadkach granicznych zaokrąglamy w dół).
5. Termin oddania pdf-ów - 31 maja (przez email) [przedłużono do 7 czerwca].