Geometria obliczeniowa 2010

Czwartek 1705 - 1845 C-11/P.01 wykład

Czwartek 1515 - 1655 TN C-7/303 ć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 (w przybliżeniu)

  1. Wprowadzenie. (24-02-2010)
    [Podstawowe pojęcia; szukanie przecięć w zbiorze docinków.]
  2. Triangulacja wielokątów. (4-03-2010)
    [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. (11-03-2010)
    [Podział na trapezy; podział na wielokąty monotoniczne; podział na wielokąty wypukłe.]
  4. Przecięcia. (18-03-2010)
    [Przecięcia zbioru odcinków; 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. (25-03-2010)
    [Kd-drzewa; drzewa obszarów.]
  6. Lokalizacja punktu. (31-03-2010)
    [Sprawdzenie czy punkt jest wewnątrz wielokąta; podział płaszczyzny na pasy; mapy trapezoidów.]
  7. Otoczki wypukłe. (8-04-2007)
    [Algorytmy Grahama, Jarvisa i „dziel i rządź”; granica dolna.]
  8. Diagramy Voronoi. (15-04-2010)
    [Własności diagramów Voronoi; algorytmy wyznaczania diagramów Voronoi: „dziel i rządź” oraz z prostą zamiatającą.]
  9. Triangulacja Delaunay-a. (22-04-2010)
    [Podstawowe własności; związek z diagramami Voronoi; minimalne euklidesowe drzewo rozpinające; para najdalszych punktów w zbiorze.]
  10. Przemieszczanie obiektów. (29-04-2010)
    [Robot punktowy; sumy Minkowskiego.]
  11. Grafy widzialności. (6-05-2010)
    [Obliczanie grafu widzialności; najkrótsza ścieżka dla robota.]
  12. Dualizacja liniowa i problemy z nią związane. (20-05-2010)
    [Dualizacja liniowa; problem wyważenia; problem mediany zbioru; problem „kanapki z szynką”.]
  13. Dualizacja liniowa i problemy z nią związane (cd). (27-05-2010)
    [Dualizacja liniowa; problem wyważenia; problem mediany zbioru; problem „kanapki z szynką”.]
  14. Posumowanie wykładu. (1-06-2010)
  15. Kolokwium zaliczeniowe. (10-06-2010)

Lista zadań


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


Valid XHTML 1.1! Valid CSS!

Maciej.Gebala@pwr.edu.pl