SubjectsSubjects(version: 850)
Course, academic year 2019/2020
   Login via CAS
Combinatorial and Computational Geometry I - NDMI009
Title in English: Kombinatorická a výpočetní geometrie I
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2019 to 2019
Semester: winter
E-Credits: 6
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech
Teaching methods: full-time
Additional information:
Guarantor: Mgr. Jan Kynčl, Ph.D.
doc. RNDr. Pavel Valtr, Dr.
Class: Informatika Bc.
Kombinatorická geometrie a geom. algorit
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: T_MUUK (31.01.2001)
Discrete geometry investigates combinatorial properties of geometric objects such as finite point sets or convex sets in Euclidean spaces. Computational geometry considers the design of efficient algorithms for computing with geometric configurations, and discrete geometry serves as its mathematical foundation. Part I of the course is a concise introduction. The contents of Part II varies among the years, each year covering a few selected topics in more depth.
Aim of the course -
Last update: T_KAM (20.04.2008)

Serves as a mathematical foundation for areas using geometric computations (e.g., computer graphics, geometric optimization) and develops geometric intuition and imagination.

Course completion requirements -
Last update: Mgr. Jan Kynčl, Ph.D. (12.10.2017)

The credit for the exercise is given after obtaining at least 30 points for solving the school and home problems. The nature of the conditions do not allow repeated attempts for obtaining the credit. Obtaining the credit is necessary before the exam.

Literature -
Last update: Mgr. Jan Kynčl, Ph.D. (06.10.2015)

J. Matoušek: Lectures on Discrete Geometry, Springer, 2002

J. Pach, P. Agarwal: Combinatorial Geometry, Cambridge University Press 1995

M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational geometry: Algorithms and Applications, Springer-Verlag 1997

Teaching methods -
Last update: Mgr. Jan Kynčl, Ph.D. (24.02.2016)

The exercises consist in individual solving of problems assigned during the semester. More information:

Requirements to the exam -
Last update: doc. RNDr. Pavel Valtr, Dr. (13.10.2017)

There will be oral exam with time for preparation of the answers. The material required for the exam will be the same as taught in the lecture. The exam may include easier or moderately difficult problems from these topics.

Syllabus -
Last update: Mgr. Jan Kynčl, Ph.D. (13.06.2019)

Basic theorems on convex sets (Helly, Radon, Caratheodory, separation).

Minkowski's theorem on lattice points in convex bodies.

Point-line incidences.

Geometric duality. Convex polytopes: definition, basic properties,

maximum number of faces.

Voronoi diagrams.

Hyperplane arrangements.

Introduction to algorithms of computational geometry. Randomized incremental


Registration requirements -
Last update: doc. RNDr. Martin Tancer, Ph.D. (14.10.2016)

The lecture will be taught alternatingly in Czech (years 2017/2018, 2019/2020, ...) and in English (years 2016/2017, 2018/2019, ...) This may be changed in some year only if all attendants agree with the change.

Charles University | Information system of Charles University |