Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)
The primary goal of computational geometry is the construction of algorithms and data structures for solving
problems stated in terms of basic geometric objects, such as points, lines, polygons, convex polytopes and others.
A lot of emphasis is given on the best possible asymptotic comlexity of the algorithms. The main application areas
include computer graphics and data visualisation, computer vision, design of 3D objects and robotics. Knowledge
in the scope of the course "Introduction to Combinatorial and Computational Geometry" is assumed.
Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)
Hlavním cílem výpočetní geometrie je konstrukce algoritmů a datových struktur pro řešení problémů týkajících se
základních geometrických objektů (bodů, přímek, polygonů, konvexních mnohostěnů apod.). Velký důraz je kladen
na co nejlepší asymptotickou složitost algoritmů. Hlavními oblastmi aplikací jsou počítačová grafika a vizualizace
dat, počítačové vidění, design 3D objektů či robotika. Předpokládají se znalosti v rozsahu předmětu
"Základy kombinatorické a výpočetní geometrie".
Literature -
Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)
Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars, Computational geometry: Algorithms and applications, Third edition, Springer-Verlag, Berlin, 2008, ISBN: 978-3-540-77973-5. [http://www.cs.uu.nl/geobook/]
Franco Preparata and Michael Shamos, Computational geometry: An introduction, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985, ISBN: 0-387-96131-3
Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)
Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars, Computational geometry: Algorithms and applications, Third edition, Springer-Verlag, Berlin, 2008, ISBN: 978-3-540-77973-5. [http://www.cs.uu.nl/geobook/]
Franco Preparata and Michael Shamos, Computational geometry: An introduction, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985, ISBN: 0-387-96131-3
Syllabus -
Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)
models of computation (Real RAM)
convex hull in R^2 and R^3
triangulation of a polygon
orthogonal range searching in R^2 and R^d
point localization and trapezoid decomposition
construction of the Voronoi diagram and the Delaunay triangulation
z-buffer, binary space partition, BSP tree
quadtree
visibility graph
Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)
modely výpočtu (Real RAM)
konvexní obal v R^2 a v R^3
triangulace mnohoúhelníka
konstrukce arrangementu přímek
orthogonal range searching v R^2 a v R^d
lokalizace bodu a lichoběžníkový rozklad
konstrukce Voroného diagramu a Delaunayovy triangulace
