Geometria obliczeniowa 2007

Wtorek 9¹⁵ - 11⁰⁰ C-11/P.01 wykład

Kolokwium zaliczeniowe odbędzie się na wykładzie 12 czerwca.

Kolokwium poprawkowe odbędzie się 25 czerwca o godz. 9¹⁵ w sali C-11/P.01.

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. (20-02-2007)
   [Podstawowe pojęcia; szukanie przecięć w zbiorze docinków.]
2. Triangulacja wielokątów. (27-02-2007)
   [Problem galerii i strażników; triangulacja przekątnymi wielokątów prostych; triangulacja przekątnymi wielokątów monotonicznych.]
3. Podział wielokąta na wielokąty monotoniczne. (6-03-2007)
   [Podział na trapezy; podział na wielokąty monotoniczne; podział na wielokąty wypukłe.]
4. Programowanie liniowe. (13-03-2007)
   [Część wspólna dwóch wielokątów wypukłych; przecięcie zbioru półpłaszczyzn; dwuwymiarowe programowanie liniowe.]
5. Przeszukiwanie obszarów. (20-03-2007)
   [Kd-drzewa; drzewa obszarów.]
6. Lokalizacja punktu. (27-03-2007)
   [Sprawdzenie czy punkt jest wewnątrz wielokąta; podział płaszczyzny na pasy; mapy trapezoidów.]
7. Otoczki wypukłe. (3-04-2007)
   [Algorytmy Grahama, Jarvisa i „dziel i rządź”; granica dolna.]
8. Diagramy Voronoi. (17-04-2007)
   [Własności diagramów Voronoi; algorytmy wyznaczania diagramów Voronoi: „dziel i rządź” oraz z prostą zamiatającą.]
9. Triangulacja Delaunay-a. (24-04-2007)
   [Podstawowe własności; związek z diagramami Voronoi; randomizacyjny algorytm obliczania DT; minimalne euklidesowe drzewo rozpinające; para najdalszych punktów w zbiorze.]
10. Przemieszczanie obiektów. (8-05-2007)
    [Robot punktowy; sumy Minkowskiego.]
11. Grafy widzialności. (22-05-2007)
    [Obliczanie grafu widzialności; najkrótsza ścieżka dla robota.]
12. Dualizacja liniowa i problemy z nią związane. (29-05-2007)
    [Dualizacja liniowa; problem wyważenia; problem mediany zbioru; problem „kanapki z szynką”.]
13. Posumowanie wykładu. (5-06-2007)
    

Listy zadań

• Lista zadań nr 1 do wykładów 1-4
• Lista zadań nr 2 do wykładów 5-6
• Lista zadań nr 3 do wykładów 7-9
• Lista zadań nr 4 do wykładów 10-11
• Lista zadań nr 5 do wykładów 12-13

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ą 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 wykład.