| |
Computational Geometry (36VGE)
course in Czech language
full-time study course, currently not teaching
Number of teaching periods (lectures + seminars): 2+2
Termination: Credit, examination
Summary:
| |
Principles of computational geometry (CG), data structures and paradigms, methods of geometric search, convex polygons and hulls, applications of convex hull, proximity problems, Voronoi diagrams, triangulation, efficient intersection algorithms, intersection of semispaces and polygonal regions, geometry of rectangles, dual mappings and spaces, convex hull in dual space, algorithms of computer graphics and CG.
|
Course Syllabus:
| |
- Subject of computational geometry (CG)
- Data structures and paradigms in CG
- Methods of geometric searching
- Convex hulls and convex polygons
- Applications of convex hull
- Proximity problem
- Voronoi diagram
- Triangulation of polygons
- Intersections of segments and lines
- Intersection of semispaces and polygonal regions
- Geometry of rectangles
- Dual mappings and spaces, convex hull in dual space
- Algorithms of computer graphics & computational geometry
- Application of CG in Geographic Information Systems
|
Seminar syllabus:
| |
- Assignment of topics for individual presentations
- Representation of Planar graph, search trees
- Interval search, BSP trees
- Searching in planar subdivision
- Convex hull in 2D
- Convex hull in 3D. Diameter of a point set.
- Construction of higher order Voronoi diagram( VD). Generalization of VD
- Proximity problems solved by the Voronoi diagram
- Delaunay triangulation and minimal weight triangulation
- Application of triangulations, stratification of the triangulation.
- Algebra of polygonal areas. Searching of the polygon core.
- Construction of the boundary of unified rectangles, intersection of rectangles.
- Application of algorithms and methods of Computational Geometry in Computer Graphics.
- Crediting
|
Literature:
| |
[1] Preperata, F.P., Shamos, M.I.: Computational Geometry An Introduction. Springer-Verlag, Berlin 1985
[2] Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin 1987
[3] de Berg, M.,van Kreveld, M., Overmars, M., Schvarzkopf, O.: Computational Geometry. Springer-Verlag, Berlin 1997
|
|
 
|
