Geometria obliczeniowa 2022

Poniedziałek 1115 - 1300 C-5/2 wykład

Wtorek 1315 - 1500 C-5/3 ć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. (28-02-2022) [1,rozdział 1 i 2]
    [Podstawowe pojęcia. Przecięcia odcinków.]
  2. Triangulacja wielokątów. (07-03-2022) [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. (14-03-2022) [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. (21-03-2022) [1,rozdział 4]
    [Część wspólna dwóch wielokątów wypukłych. Przecięcie zbioru półpłaszczyzn. Jądro wielokąta prostego. Dwuwymiarowe programowanie liniowe.]
  5. Przeszukiwanie obszarów. (28-03-2022) [1,rozdział 5] [2,rozdział 2.3]
    [Kd-drzewa, drzewa obszarów.]
  6. Lokalizacja punktu. (04-04-2022) [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. (11-04-2022) [1,rozdział 11] [2,rozdział 3]
    [Algorytmy Grahama, Jarvisa i „dziel i rządź”; granica dolna.]
  8. Diagramy Voronoi. (25-04-2022) [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 (09-05-2022) [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. (16-05-2022) [1,rozdział 13 i 15]
    [Robot punktowy; obliczanie grafu widzialności; najkrótsza ścieżka dla robota.]
  11. Przemieszczanie obiektów. (cd) (23-05-2022) [1,rozdział 13]
    [Sumy Minkowskiego. Robot niepunktowy.]
  12. Dualizacja liniowa i problemy z nią związane. (30-05-2022) [Szkic notatek]
    [Dualizacja liniowa; prosta przecinająca n odcinków; problem wyważania.]
  13. Dualizacja liniowa ... (cd) (06-06-2022) [Szkic notatek]
    [Problem mediany zbioru; problem „kanapki z szynką”.]
  14. Algorytmy równoległe w geometrii obliczeniowej. (13-06-2022) [3,rozdział 30]
  15. Kolokwium zaliczeniowe. (21-06-2022 - zamiana ćwiczeń z wykładem) [Przykładowe kolokwium]

Ćwiczenia

Lista zadań

  1. Zad. 1-4 (01-03-2022)
  2. Zad. 5-8 (08-03-2022)
  3. Zad. 9-12 (15-03-2022)
  4. Zad. 13-16 (22-03-2022)
  5. Zad. D1-D4 (29-03-2022)
  6. Zad. 17-19 (05-04-2022)
  7. Zad. 20-23 (12-04-2022)
  8. Zad. 24-27 (26-04-2022)
  9. Zad. 28-30 (10-05-2022)
  10. Zad. 31-32 (17-05-2022)
  11. Zad. 33-35 (24-05-2022)
  12. Zad. 36-40 (31-05-2022)
  13. Zad. 41-44 (07-06-2022)
  14. Zad. 45-49 (14-06-2022)

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 przydzielone) jest traktowane jako aktywność.


Valid XHTML 1.1! Valid CSS!

Maciej.Gebala@pwr.edu.pl