Advanced Computational Geometry

Login to KOS for course enrollment Display time-table
Code Completion Credits Range
XP39CG ZK 4 2P+1C+4D
Petr Felkel (guarantor)
Petr Felkel (guarantor)
Department of Computer Graphics and Interaction

The aim of the course is to deepen the knor,vledge of computational geometry. The course is designed primarily for

students who have a dissertation topic related to data structures in computer graphics and effective w'ork with them. The

starting point of the study u'ill be chapters from the compulsory literature, specific topics will be based on scientific

articles that develop the issue. Students will have the latest articles on the subject and will creatively process the theme.

This is mainly about mastering the methodology of scientific r,r,ork taking into account the subject of the dissertation.

Precisely this aspect (the methodology ofscientific rvork in the given field) is one ofthe added values ofthe subject. The

subject, n'ith its theoretical character, invites directly to the above-defined concept.

Syllabus of lectures:

1. Randomized algorithms in CG (dynamic algorithms)

2. Randomized algorithms in CG (random sampling)

3. Simplex range searching (partition trees) 4. Simplex range searching (cutting trees)

5. Data-stream algorithms in CG

6. Kinetic data structures

7. Kinetic data structures

8. Sublinearalgorithms

9. Sublinearalgorithms

10. Polygon decomposition

11. Application of CG to GIS

12. Application of CG to GIS

13. Application of CG to Data Visualization

14. Reserve

Syllabus of tutorials:
Study Objective:
Study materials:

Mulmuley: Computational Geometry, An Introduction Through Randomized Algorithms, Prentice-Hall, 1994.

Berg, M. de, Cheong, O., Kreveld, M. van, Overmars, M.: Computational Geometry. Algorithms and Applications,

Springer-Verlag, Berlin, 3rd ed., 2008.

J.R. Sack, J. Umrtia: Handbook of Computational Geometry, Elsevier, 1999.

Conference and journal papers

Time-table for winter semester 2019/2020:
Time-table is not available yet
Time-table for summer semester 2019/2020:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2020-01-22
For updated information see http://bilakniha.cvut.cz/en/predmet6039906.html