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í.
Poslední úprava: T_KSVI (22.05.2003)
The course deals with methods and data structures from the algorithmic computational geometry, usable for geometrically formulated problems in computer graphics and its applications, but also pattern recognition, database systems, artificial intelligence, statistics etc. Examples of solved problems are as follows: geometric search, triangulation, mutual position of geometric objects. Examples of presented methods are as follows: sweeping, duality, divide and conquer, Voronoi diagrams.
Literatura
Poslední úprava: prof. Dr. Ing. Ivana Kolingerová (21.06.2018)
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: prof. Dr. Ing. Ivana Kolingerová (20.06.2018)
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
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ě
Poslední úprava: prof. Dr. Ing. Ivana Kolingerová (20.06.2018)
1. Introduction, examples of problems solvable by a geometric approach, application areas, fundamental techniques (e.g., divide and conquer, sweeping, locus approach etc.), complexity and evaluation of algorithms, degeneracy and robustness, influence of preprocessing to complexity, programming of geometrically oriented problems in conditions of a limited numerical accuracy
2. Geometric searching - point location, range searching, plane subdivision search, applications
