Sylabus
Základní věty o konvexních množinách (Hellyho, Radonova, o oddělování).
Minkowského věta o mřížkách.
Incidence bodů a přímek.
Geometrická dualita.
Definice a základní vlastnosti konvexních mnohostěnů.
Kombinatorická složitost konvexních mnohostěnů.
Voroného diagramy.
Komplexy indukované nadrovinami.
Arrangementy algebraických ploch, pseudopřímek.
Anotace
Výpočetní geometrie se zabývá návrhem efektivních algoritmů pro geometrické problémy v rovině i ve vícedimenzionálním prostoru (např. je-li dáno N bodů v rovině, jak co nejefektivněji najít dvojici bodů s nejmenší vzdáleností). Takové problémy jsou motivovány aplikacemi v počítačové grafice, prostorovém modelování (např. molekul, budov, součástek), geografických informačních systémech apod.
Při analýze takových algoritmů se potřebuje kombinatorická geometrie, studující kombinatorické vlastnosti geometrických konfigurací, konvexních množin a pod. Výsledky jsou důležité i z čistě matematického hlediska, např. v teorii čísel.
V této úvodní přednášce se probírají základní pojmy a metody, s důrazem na matematický základ (t.j. jen s minimem materiálu o datových strukturách apod).