Základy kombinatorické a výpočetní geometrie

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