Vymezení obsahu výpočetní geometrie (VG). Datové struktury a paradigmata VG
Metody geometrického vyhledávání
Konvexní polygony a konvexní obálka. Praktické aplikace konvexní obálky
Problém "nejbližších" (proximity)
Voronoiovy diagramy
Problém triangulace a triangulační algoritmy
Efektivní algoritmy výpočtu průsečíků. Průniky poloprostorů a polygonálních oblastí
Geometrie rovnoběžníků
Duální zobrazení a duální prostory
Aplikace výpočetní geometrie
Doporučená literatura
Preperata, F.P., Shamos, M.I.: Computational Geometry An Introduction. Springer-Verlag, Berlin 1985
Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin 1987
de Berg, M.,van Kreveld, M., Overmars, M., Schvarzkopf, O.: Computational Geometry. Springer-Verlag, Berlin 1997
Anotace
Cílem výpočetní geometrie je analýza a návrh efektivních algoritmů pro určování vlastností a vztahů geometrických objektů. Řeší se problémy geometrického vyhledávání, problém polohy bodu, hledání konvexní obálky množiny bodů v d-rozměrném prostoru, problém hledání blízkých bodů, výpočet průniků polygonálních oblastí a poloprostorů, geometrie rovnoběžníků. Výpočetní geometrie nachází uplatnění nejen v geometrických aplikacích, ale i v obecných vyhledávacích problémech.
