Kombinatorická a výpočetní geometrie I - NDMI009

• Anglický název: Combinatorial and Computational Geometry I
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2008 do 2013
• Semestr: zimní
• E-Kredity: 6
• Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Garant: prof. RNDr. Jiří Matoušek, DrSc.; doc. RNDr. Pavel Valtr, Dr.
• Vyučující: doc. RNDr. Martin Balko, Ph.D.; prof. RNDr. Jiří Matoušek, DrSc.; doc. RNDr. Pavel Valtr, Dr.
• Třída: Informatika Bc.; Kombinatorická geometrie a geom. algorit; M Mgr. MSTR; M Mgr. MSTR > Povinně volitelné
• Kategorizace předmětu: Informatika > Diskrétní matematika
• Je neslučitelnost pro: NGEM020
• Je záměnnost pro: NGEM020

Anotace

čeština

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: ()

angličtina

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.

Poslední úprava: T_MUUK (31.01.2001)

Cíl předmětu

čeština

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)

angličtina

Serves as a mathematical foundation for areas using geometric computations (e.g., computer graphics, geometric optimization) and develops geometric intuition and imagination.

Poslední úprava: T_KAM (20.04.2008)

Literatura

čeština

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: Kynčl Jan, doc. Mgr., Ph.D. (06.10.2015)

angličtina

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: Tancer Martin, prof. RNDr., Ph.D. (06.10.2015)

Sylabus

čeština

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

Kombinatorická složitost konvexních mnohostěnů.

Voroného diagramy (Voronoi diagrams).

Komplexy indukované nadrovinami (hyperplane arrangements).

Uvod do algoritmu vypocetni geometrie. Pravděpodobnostní inkrementální algoritmy.

Poslední úprava: Balko Martin, doc. RNDr., Ph.D. (25.02.2016)

angličtina

Basic theorems on convex sets (Hellyho, Radon, Caratheodory, separation).

Minkowski's theorem on lattice points in convex bodies.

Line-point incidences.

Geometric duality. Convex polytopes: definition, basic properties,

maximum number of faces.

Voronoi diagrams.

Hyperplane arrangements.

Introduction to algorithms of computational geometry. Randomized incremental

algorithms.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (13.06.2019)