Geometria obliczeniowa 2012

Środa 17⁰⁵ - 18⁴⁵ D-1/312b wykład

Środa 18⁵⁵ - 19⁴⁰ 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 i ćwiczeń (w przybliżeniu)

1. Wprowadzenie. (03-10-2012 - 3h)
   [Podstawowe pojęcia; szukanie przecięć w zbiorze odcinków.]
2. Triangulacja wielokątów. (10-10-2012 - 3h)
   [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. Przecięcia. Przeszukiwanie obszarów. (17-10-2012 - 3h)
   [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; Kd-drzewa; drzewa obszarów.]
4. Ćwiczenia. Zadania 1-10. (24-10-2012 - 3h)
5. Godziny rektorskie. (31-10-2012 - 3h)
6. Lokalizacja punktu. Otoczki Wypukłe (7-11-2012 - 3h)
   [Sprawdzenie czy punkt jest wewnątrz wielokąta; podział płaszczyzny na pasy; mapy trapezoidów; algorytmy Grahama, Jarvisa i „dziel i rządź”; granica dolna.]
7. Diagramy Voronoi i Triangulacja Delaunay-a (14-11-2012 - 3h)
   [Własności diagramów Voronoi; algorytmy wyznaczania diagramów Voronoi: „dziel i rządź” oraz z prostą zamiatającą; podstawowe własności triangulacji Delaunay-a; związek z diagramami Voronoi; minimalne euklidesowe drzewo rozpinające; para najdalszych punktów w zbiorze.]
8. Ćwiczenia. Zadania 11-18. (21-11-2012 - 3h)
9. Przemieszczanie obiektów. Grafy widzialności. (28-11-2012)
   [Robot punktowy; sumy Minkowskiego. Obliczanie grafu widzialności; najkrótsza ścieżka dla robota.]
10. Ćwiczenia. Zadania 19-23. (5-12-2012 - 3h)
11. Dualizacja liniowa i problemy z nią związane. (12-12-2012)
    [Dualizacja liniowa; problem wyważenia; problem mediany zbioru; problem „kanapki z szynką”; problem wyważenia.]
12. Ćwiczenia. Zadania 24-30. (19-12-2012 - 3h)
13. Algorytmy równoległe w geometrii obliczeniowej (9-01-2013 - 3h)
14. Ćwiczenia. Zadania 31-34. (16-01-2013 - 3h)
15. Kolokwium zaliczeniowe. (23-01-2013)

Listy zadań

• Lista zadań do wykładu

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.