Okruhy ke zkoušce z VAM

Doc. dr. ing. I. Kolingerová

1. Základy výpočetní geometrie

prostředky a problémy výpočetní geometrie, základní užívané techniky, oblasti aplikací, složitost algoritmů a její použití k hodnocení vhodnosti a kvality algoritmu, citlivost na výstup

2. Geometrické vyhledávání

lokace bodu, hledání intervalů, aplikace

3. Konvexní obálky

2D, 3D, aplikace

4. Voronoiovy diagramy

vlastnosti, aplikace, konstrukce, zobecnění

5. Triangularizace

Delaunayova, žravá, triangulace s omezením, konvexního polygonu, jednoduchého polygonu, monotónního polygonu, tetrahedronizace

6. Dělení polygonu

na lichoběžníky, na konvexní polygony

7. Problém strážců galerie

8. Průsečíky a průniky

polygony, úsečky, využití duality pro testy průniků, aplikace

9. Plánování pohybu

vzájemná viditelnost a její využití pro konstrukci nejkratší cesty bodového robota, posun disku, konvexního polygonu a žebříku v 2D

10. Trendy a výhledy ve výpočetní geometrii – rámcová představa o současných problémech a nejnovějších trendech v dané oblasti

11. Algoritmické řešení úloh na základě probíraných technik