Sylabus
- modely výpočtu (Real RAM)
- konvexní obal v R^2 a v R^3
- triangulace mnohoúhelníka
- konstrukce arrangementu přímek
- orthogonal range searching v R^2 a v R^d
- lokalizace bodu a lichoběžníkový rozklad
- konstrukce Voroného diagramu a Delaunayovy triangulace
- z-buffer, binární rozklad prostoru, BSP strom
- quadtree
- viditelnostní graf
Anotace
Hlavním cílem výpočetní geometrie je konstrukce algoritmů a datových struktur pro řešení problémů týkajících se základních geometrických objektů (bodů, přímek, polygonů, konvexních mnohostěnů apod.). Velký důraz je kladen na co nejlepší asymptotickou složitost algoritmů. Hlavními oblastmi aplikací jsou počítačová grafika a vizualizace dat, počítačové vidění, design 3D objektů či robotika. Předpokládají se znalosti v rozsahu předmětu
"Základy kombinatorické a výpočetní geometrie".