SubjectsSubjects(version: 830)
Course, academic year 2017/2018
   Login via CAS
The Student Information System will be shut down from 18th Aug 2018 18:00 until 19th Aug 2018 2:00 due to a scheduled maintenance. 
Applied Computational Geometry - NPGR016
Title in English: Aplikovaná výpočetní geometrie
Guaranteed by: Department of Software and Computer Science Education (32-KSVI)
Faculty: Faculty of Mathematics and Physics
Actual: from 2016
Semester: summer
E-Credits: 5
Hours per week, examination: summer s.:2/1 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Additional information:
Note: enabled for web enrollment
Guarantor: prof. Dr. Ing. Ivana Kolingerová
Class: DS, softwarové systémy
Informatika Bc.
Informatika Mgr. - volitelný
Classification: Informatics > Computer Graphics and Geometry
Annotation -
Last update: 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.
Course completion requirements -
Last update: prof. Dr. Ing. Ivana Kolingerová (21.06.2018)

Conditions are given at

Literature -
Last update: prof. Dr. Ing. Ivana Kolingerová (21.06.2018)

1. O' Rourke, Joseph: Computational Geometry in C, Cambridge University Press, 1st edition, 1994 or 2nd edition, 2000

2. de Berg, Mark, van Kreveld, Marc, Overmars, Mark, Schwarzkopf, Otfried: Computational Geometry, Algorithms and Applications, Springer Verlag, 1st edition, 1997 or 2nd edition, 2001

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

4. PowerPoint presentation files on the course home page and other materials provided by the teacher in the printed form

Syllabus -
Last update: prof. Dr. Ing. Ivana Kolingerová (20.06.2018)

1. Computational geometry as a tool for geometric and graphical applications

2. Geometric search - point location, range search

3. Convex hulls in 2D, 3D

4. Voronoi diagrams - properties, construction

5. Voronoi diagrams - generalizations and applications

6. Planar triangulations (Delaunay, greedy, data dependent, constrained, minimum weight, multicriterially optimized) and their applications

7. Tetrahedronizations and their applications

8. Polygon triangulation and decomposition (into trapezoids, convex polygons), art gallery problem

9. Medial axis

10. Surface reconstruction from scattered points

11. Intersections (line segments, polygons, halfplanes, dualities)

12. In case of interest and free time: scientific writing, presentations, creativity

Charles University | Information system of Charles University |