Výpočetní geometrie

Předmět je náhradou za:

Výpočetní geometrie (X39VGE)

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra počítačů

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ů.

Požadavky:

Osnova přednášek:

1. Vymezení obsahu výpočetní geometrie (VG)

2. Datové struktury a paradigmta VG

3. Metody geometrického vyhledávání

4. Konvexní polygony a konvexní obálka

5. Praktické aplikace konvexní obálky

6. Problém „nejbližších“ (proximity)

7. Voronoiovy diagramy

8. Problém triangulace a triangulační algoritmy

9. Efektivní algoritmy výpočtu průsečíků

10. Průniky poloprostorů a polygonálních oblastí

11. Geometrie rovnoběžníků

12. Duální zobrazení a duální prostory

13. Konvexní obálka v duálním prostoru

14. Numerická stabilita geometrických predikátů.

Osnova cvičení:

1. Výběr témat samostatných referátů studentů.

2. Reprezentace planárního grafu, vyhledávací stromy.

3. Vyhledávání na intervalovou shodu, BSP stromy.

4. Vyhledávání v planárním dělení.

5. Algoritmus konstrukce konvexní obálky.

6. Algoritmy konstrukce konvexní obálky v 3D prostoru. Průměr množiny bodů.

7. Konstrukce Voronoiova diagramu vyššího řádu. Zobecnění Voronoiova diagramu

8. Problémy proximity a jejich řešení pomocí Voronoiova diagramu.

9. Algoritmy Delaunnayovy triangulace a triangulace s nejmenší váhou.

10. Aplikace triangulace, stratifikace triangulace.

11. Algebra polygonálních oblastí, nalezení jádra polygonální oblasti

12. Algoritmus nalezení obvodu sjednocených rovnoběžníků, průnik rovnoběžníků.

13. Aplikace algoritmů a metod výpočetní geometrie v počítačové grafice a robotice.

14. Zápočet.

Cíle studia:

Studijní materiály:

[1] Preperata, F.P., Shamos, M.I.: Computational Geometry An Introduction. Springer-Verlag, Berlin 1985

[2] Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin 1987

[3] de Berg, M.,van Kreveld, M., Overmars, M., Schvarzkopf, O.: Computational Geometry. Springer-Verlag, Berlin 1997

Poznámka:

Rozsah výuky v kombinované formě studia: 14+4

Typ cvičení: s

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: