Geometria obliczeniowa 2014

Poniedziałek 15¹⁵ - 16⁵⁵ D-1/312B wykład

Poniedziałek 17⁰⁵ - 18⁴⁵ D-1/312B ćwiczenia

Wyniki kolokwium
Poprawa 1 lipca, godz. 18¹⁵, A-1/329.

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. (03-03-2014)
   [Podstawowe pojęcia; szukanie przecięć w zbiorze odcinków.]
2. Triangulacja wielokątów. (10-03-2014)×2
   [Problem galerii i strażników; triangulacja przekątnymi wielokątów wypukłych; triangulacja przekątnymi wielokątów monotonicznych; triangulacja przekątnymi wielokątów prostych; podział na trapezy; podział na wielokąty monotoniczne; podział na wielokąty wypukłe.]
3. jw.
4. Przecięcia. (17-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.]
5. Przeszukiwanie obszarów. (24-03-2014)
   [Kd-drzewa; drzewa obszarów.]
6. Lokalizacja punktu. (31-03-2014)
   [Sprawdzenie czy punkt jest wewnątrz wielokąta; podział płaszczyzny na pasy; mapy trapezoidów.]
7. Otoczki Wypukłe. (31-03-2014)
   [Algorytmy Grahama, Jarvisa i „dziel i rządź”; granica dolna.]
8. Diagramy Voronoi. (7-04-2014)
   [Własności diagramów Voronoi; algorytmy wyznaczania diagramów Voronoi: „dziel i rządź” oraz z prostą zamiatającą.]
9. Triangulacja Delaunay-a (14-04-2014)
   [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. (28-04-2014)
    [Robot punktowy; obliczanie grafu widzialności; najkrótsza ścieżka dla robota.]
11. Przemieszczanie obiektów. (cd) (5-05-2014)
    [Sumy Minkowskiego.]
12. Dualizacja liniowa i problemy z nią związane. (12-05-2012)
    [Dualizacja liniowa; problem wyważenia; problem mediany zbioru; problem „kanapki z szynką”; problem wyważenia.]
13. Dualizacja liniowa ... (cd) (19-05-2014)
14. Algorytmy równoległe w geometrii obliczeniowej na przykłądzie otoczki wypukłej. (26-05-2014)
15. Kolokwium zaliczeniowe. (16-06-2014)

Ćwiczenia i listy zadań

1. Lista zadań nr 1(03-03-2014)
2. Lista zadań nr 2(17-03-2014)
3. Lista zadań nr 3(24-03-2014)
4. Lista zadań nr 4(7-04-2014)
5. Lista zadań nr 5(14-04-2014)
6. Lista zadań nr 6(28-04-2014)
7. Lista zadań nr 7(5-05-2014)
8. Lista zadań nr 8(12-05-2014)
9. Lista zadań nr 9(19-05-2014)
10. Lista zadań nr 10(26-05-2014)
11. Oddawanie przydzielonych zadań (2-06-2014)
12. Oddawanie przydzielonych zadań (2-06-2014)
13. Oddawanie przydzielonych zadań (9-06-2014)
14. Oddawanie przydzielonych zadań (9-06-2014)

Ostateczny termin oddania zadań: 9 czerwca. Przydział zadań (3 ost. cyfry indeksu - numery zadań;): 117 - 6,19,30,41; 345 - 11,25,40,47; 374 - 13,26,39,46; 537 - 12,24,37; 656 - 1,17,28; 658 - 10,23,29; 800 - 7,22,29,44; 814 - 5,17,28,42; 817 - 4,13,36,41; 844 - 4,18,30,46; 845 - 8,26,36,43; 859 - 9,21,34,47; 870 - 15,27,40; 874(K) - 6,20,35,48; 874(P) - 3,18,37,43; 882(B) - 12,14,31,45; 882(K) - 2,20,33,48; 883 - 8,22,33,49; 897 - 11,23,38; 901 - 16,27,39; 925 - 1,24,34; 927 - 14,25,38; 935 - 10,19,32; 949 - 3,15,35,49; 966 - 9,21,32,44; 968 - 7,16,31,42;

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.