PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Aplikovaná výpočetní geometrie - NPGR016
Anglický název: Applied Computational Geometry
Zajišťuje: Katedra softwaru a výuky informatiky (32-KSVI)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2016
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/1 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Další informace: http://iason.zcu.cz/~kolinger/vyukaUK.html
Poznámka: povolen pro zápis po webu
Garant: prof. Ing. Ivana Kolingerová, CSc.
Třída: DS, softwarové systémy
Informatika Bc.
Informatika Mgr. - volitelný
Kategorizace předmětu: Informatika > Počítačová grafika a geometrie
Anotace -
Poslední úprava: T_KSVI (22.05.2003)

Předmět se zabývá postupy a datovými strukturami z oblasti algoritmické výpočetní geometrie využitelnými pro řešení geometricky formulovaných úloh především z oblasti počítačové grafiky a jejích aplikací, dále např. rozpoznávání, databázových systémů, umělé inteligence, statistiky i jiných oblastí. Příklady řešených problémů jsou geometrické vyhledávání, triangulace, vzájemná poloha geometrických objektů. Příklady užitých metod jsou zametání, dualita, rozděl a panuj, Voronoiovy (Voroného) diagramy. Cvičení: rozbor algoritmů a návrh nových a prezentace studentských prací.
Literatura
Poslední úprava: KOLING (27.04.2005)

1. O' Rourke, Joseph: Computational Geometry in C, Cambridge University Press, 1.vydání, 1994 nebo 2.vydání, 2000

2. de Berg, Mark, van Kreveld, Marc, Overmars, Mark, Schwarzkopf, Otfried: Computational Geometry, Algorithms and Applications, Springer Verlag, 1.vydání, 1997 nebo 2.vydání, 2001

3. Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction, Springer-Verlag, New York Berlin Heidelberg Tokyo, 1985

4. Podklady přednášek v PowerPoint poskytnuté vyučujícím a další materiály distribuované na cvičení

Doporučuje se znalost angličtiny na úrovni dovolující studovat anglické prameny.

Sylabus -
Poslední úprava: KOLING (27.04.2005)

1. Úvod, přehled problémů řešitelných geometrickým přístupem a aplikačních oblastí, základní techniky (např. rozděl a panuj, zametací technika, geometrické místo bodů atd.), složitost a hodnocení algoritmů, robustnost algoritmů vůči singularitám, vliv předzpracování na složitost, programování geometricky orientovaných problémů v podmínkách omezené přesnosti výpočtů

2. Geometrické vyhledávání - lokace bodu, hledání intervalů, hledání v rovinném dělení, aplikace

3. Konvexní obálky - 2D, 3D, on-line problém, přibližné řešení, aplikace

4. Voronoiovy (Voroného) diagramy - vlastnosti, konstrukce, aplikace, dualizace, zobecnění

5. Triangulace množiny bodů v 2D a 3D - Delaunayova (Deloneho), greedy, s minimální váhou, multikriteriálně optimalizovaná, datově závislé triangulace

6. Triangulace polygonu, dělení polygonu (na lichoběžníky, konvexní polygony), problém "strážců galérie"

7. Průsečíky a průniky základních geometrických útvarů - úsečky, polygony, polyedry, poloprostory, booleovské operace nad polygony

8. Extrémní bod konvexního polytopu

9. Trendy, úkoly a novinky výpočetní geometrie

10. O kreativitě

 
Univerzita Karlova | Informační systém UK