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).
Poslední úprava: T_MUUK (31.01.2001)
Discrete geometry investigates combinatorial properties of geometric
objects such as finite point sets or convex sets in Euclidean spaces.
Computational geometry considers the design of efficient algorithms
for computing with geometric configurations, and discrete geometry serves
as its mathematical foundation.
Part I of the course is a concise introduction. The contents of Part II
varies among the years, each year covering a few selected topics in more depth.
Cíl předmětu -
Poslední úprava: T_KAM (20.04.2008)
Slouží jako matematický a algoritmický základ k oborům, v nichž se používají geometrické výpočty (např. počítačová grafika, geometrická optimalizace), a rozvíjí geometrické uvažování a představivost studentů.
Poslední úprava: T_KAM (20.04.2008)
Serves as a mathematical foundation for areas using geometric computations (e.g., computer graphics, geometric optimization) and develops geometric intuition and imagination.
Literatura -
Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (06.10.2015)
J. Matoušek: Kombinatorická a výpočetní geometrie, KAM Series 95-289 (preprint), možno vypůjčit v knihovně v Karlíně
J. Pach, P. Agarwal: Combinatorial Geometry, Cambridge University Press 1995
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational geometry: Algorithms and Applications, Springer-Verlag 1997
Poslední úprava: doc. RNDr. Martin Tancer, Ph.D. (06.10.2015)
J. Pach, P. Agarwal: Combinatorial Geometry, Cambridge University Press 1995
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational geometry: Algorithms and Applications, Springer-Verlag 1997
Sylabus -
Poslední úprava: doc. RNDr. Martin Balko, Ph.D. (25.02.2016)
Základní věty o konvexních množinách (Hellyho, Radonova, o oddělování).
Minkowskeho veta o mrizkach.
Incidence bodu a primek.
Geometrická dualita.
Definice a základní vlastnosti konvexních mnohostěnů.
