SubjectsSubjects(version: 953)
Course, academic year 2023/2024
   Login via CAS
Introduction to Combinatorial and Computational Geometry - NDMI009
Title: Základy kombinatorické a výpočetní geometrie
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2023 to 2023
Semester: winter
E-Credits: 5
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: English
Teaching methods: full-time
Teaching methods: full-time
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
Incompatibility : NDMX009
Interchangeability : NDMX009
Is incompatible with: NDMX009, NGEM020
Is interchangeable with: NDMX009, NGEM020
Annotation -
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.
Last update: T_MUUK (31.01.2001)
Aim of the course -

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

Last update: T_KAM (20.04.2008)
Course completion requirements -

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.

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

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

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

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

Last update: Kynčl Jan, doc. Mgr., Ph.D. (24.02.2016)
Requirements to the exam -

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.

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

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.

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

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.

Last update: Kynčl Jan, doc. Mgr., Ph.D. (30.07.2020)
Charles University | Information system of Charles University |