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.
Last update: 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í.
Literature - Czech
Last update: 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.
Syllabus -
Last update: 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
5. Triangulation of point sets in 2D and 3D - Delaunay, greedy, minimum weight triangulation, multicriteria-optimized, data dependent
6. Polygon triangulation and decomposition (into trapezoids, convex polygons), art gallery problem
7. Intersection of fundamental geometric objects - line segments, polygons, polyhedra, half-spaces, Boolean operations on polygons
8. Extreme point of a convex polytop
9. Trends, tasks and news in computational geometry
10. On creativity
Last update: 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
