Course details

# Computational Geometry (in English)

VGEe Acad. year 2023/2024 Summer semester 5 credits

Linear algebra, geometric algebra, affine an projective geometry, principle of duality, homogeneous and parallel coordinates, point in polygon testing, convex hull, intersection problems, range searching, space partitioning methods, 2D/3D triangulation, Delaunay triangulation, proximity problem, Voronoi diagrams, tetrahedral meshing, surface reconstruction, point clouds, volumetric data, mesh smoothing and simplification, linear programming.

Guarantor

Course coordinator

Language of instruction

English

Completion

Examination (written)

Time span

• 26 hrs lectures
• 26 hrs projects

Assessment points

• 51 pts final exam (24 pts written part, 27 pts test part)
• 31 pts projects
• 18 pts homework

Department

Lecturer

Instructor

Learning objectives

• Student will get acquaint with the typical problems of computational geometry.
• Student will understand the existing solutions and their applications in computer graphics and machine vision.
• Student will get deeper knowledge of mathematics.
• Student will learn the principles of geometric algebra including its application in graphics and vision related tasks.
• Student will practice programming, problem solving and defence of a small project.

• Student will learn terminology in English language.
• Student will learn to work in a team and present/defend results of their work.
• Student will also improve his programming skills and his knowledge of development tools.

Why is the course taught

This course focuses on topics and classical problems which, in small variations, students meet in other courses (e.g. computer vision or computer graphics). These topics are rather marginal with respect to the content of these courses, so there is typically not enough time to discuss them in more detail. However, their knowledge is needed in practice.
The lectures present some of the classical problems of computational geometry (nearest neighbour search, range searching, space partitioning methods, 2D/3D triangulation, Voronoi diagrams, etc.) and further deepen your theoretical background in the field of affine and projective geometry, homogeneous coordinates, quaternions, etc.

Prerequisite knowledge and skills

• Basic knowledge of linear algebra and geometry.
• Good knowledge of computer graphics principles.
• Good knowledge of basic abstract data types and fundamental algorithms.

Study literature

Syllabus of lectures

1. Introduction to computational geometry: typical problems in computer graphics and machine vision, algorithm complexity and robustness, numerical precision and stability.
2. Overview of linear algebra and geometry. Why is it necessary to know this?
3. Range searching and space partitioning methods: range tree; quad tree, k-d tree, BSP tree. Applications in machine vision.
4. Coordinate systems and homogeneous coordinates. Applications in computer graphics.
5. Point in polygon testing, polygon triangulation, convex hull in 2D/3D and practical applications.
6. Collision detection and the algorithm GJK.
7. Proximity problem: closest pair; nearest neighbor; Voronoi diagrams.
8. Affine and projective geometry. Epipolar geometry. Applications in 3D machine vision.
9. Triangulation in 2D/3D, Delaunay triangulation, tetrahedral meshing.
10. Principle of duality and its applications.
11. Surface reconstruction from point clouds and volumetric data.
12. Basics and of geometric algebra. Quaternions. Applications in computer graphics.
13. More computational geometry problems and modern trends. Linear programming: basic notion and applications; half-plane intersection.

Syllabus - others, projects and individual work of students

Team or individually assigned projects.

Progress assessment

• Preparing for lectures (readings): up to 18 points
• Realized and defended project: up to 31 points
• Written final exam: up to 51 points
• Minimum for final written examination is 17 points.
• Minimum to pass the course according to the ECTS assessment - 50 points.

The evaluation includes reading scientific articles, individual project, and the final exam.

Schedule

DayTypeWeeksRoomStartEndCapacityLect.grpGroupsInfo
Mon lecture 1., 2., 3., 5. of lectures A113 12:0013:5064 1EIT 2EIT INTE MGMe xx Bařina
Mon lecture 6., 8., 11. of lectures A113 12:0013:5064 1EIT 2EIT INTE MGMe xx Španěl
Mon lecture 10., 12., 13. of lectures A113 12:0013:5064 1EIT 2EIT INTE MGMe xx Herout
Mon lecture 2024-02-26 A113 12:0013:5064 1EIT 2EIT INTE MGMe xx Zemčík
Mon lecture 2024-03-18 A113 12:0013:5064 1EIT 2EIT INTE MGMe xx Beran
Mon exam 2024-05-13 E104 13:0014:50 1. termín
Mon other *) 2024-04-22 E112 16:0017:5060 INTE xx Bařina
Fri exam 2024-05-31 E105 13:0014:50 3. termín
Fri exam 2024-05-24 A112 14:0015:50 2. termín
It is not possible to register this class in Studis. (Some exercises may be opened later if needed, but this is not guaranteed.)

Course inclusion in study plans

Back to top