AZ (algorytmika i złożoność obliczeniowa)NG (metody numeryczne i grafika komputerowa)
Opis przedmiotu:
Celem wykładu jest zaznajomienie słuchaczy z algorytmami i strukturami danych
używanymi w dyskretnej geometrii, głownie w dwoch i trzech wymiarach.
Rozważane problemy znajdują zastosowania w grafice komputerowej,
geograficznych systemach informacyjnych (GIS), robotyce, i in.
Przy omawianiu poszczegolnych problemow i algorytmow prezentowane też będą
przykłady ich zastosowań.
**Program:**
1. Podstawowe struktury danych dla problemow geometrycznych.
2. Geometryczne szukanie; lokalizacja punktu na płaszczyźnie.
3. Metody wyznaczania otoczki wypukłej.
4. Problemy sąsiedztwa punktow i diagramy Voronoi'a.
5. Dekompozycja płaszczyzny, triangulacje.
6. Planowanie trasy robota.
7. Dualność w problemach geometrycznych.
**Wymagania:** Algorytmy i Struktury Danych