SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Introduction to Combinatorial and Computational Geometry - NDMX009
Title: Základy kombinatorické a výpočetní geometrie
Guaranteed by: Student Affairs Department (32-STUD)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
Semester: winter
E-Credits: 6
Hours per week, examination: winter s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Is provided by: NDMI009
Additional information:
Guarantor: doc. RNDr. Pavel Valtr, Dr.
doc. Mgr. Jan Kynčl, Ph.D.
Class: Informatika Bc.
Kombinatorická geometrie a geom. algorit
Classification: Informatics > Discrete Mathematics
Pre-requisite : {NXXX007, NXXX009, NXXX014, NXXX015, NXXX016, NXXX017, NXXX022, NXXX023, NXXX024, NXXX025, NXXX033}
Incompatibility : NDMI009
Interchangeability : NDMI009
Is incompatible with: NDMI009
Is interchangeable with: NDMI009
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: doc. 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: doc. 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: doc. 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. Mgr. Jan Kynčl, Ph.D. (10.10.2020)

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. The exam can also be in a distance form.

Syllabus -
Last update: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)

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

Minkowski's theorem on lattice points in convex bodies.

Line-point incidences.

Geometric duality. Convex polytopes: definition, basic properties,

maximum number of faces.

Voronoi diagrams.

Hyperplane arrangements.

Arrangements of algebraic surfaces, pseudolines.

Registration requirements -
Last update: doc. Mgr. Jan Kynčl, Ph.D. (30.07.2020)

The lecture will be taught alternatingly in Czech (2020/2021, ...) and in English (2021/2022, ...) The language may be changed in a particular year if all attendants agree with the change.

Charles University | Information system of Charles University |