University of Liege | Version française
Academic year 2014-2015Value date : 1/10/2014
Version 2013-2014
INFO2046-1  Computational geometry

Duration :  30h Th, 30h Pr
Number of credits :  
Master of science in computer science and engineering, research focus, 2nd year5
Master in Computer science, Research Focus, 2nd year6
Lecturer :  Eric Béchet
Language(s) of instruction :  
English language
Course contents :  
In many aspects in applied sciences, geometric problem do appear naturally. Solutions to those problems are not always trivial. Collision detection is one of those problems, ans it can be solved using specifically designed algorithms and data structures such as the BSP tree. The tessellation of a domain is also a non trivial geometric problem with many applications in scientific computing. One can also find other application outside the scope of applied sciences, such as geographic information systems (GIS). Generally speaking, the course focuses on discrete geometry, that is to say , we do not consider the notion of continuity, but rather focus on geometric entities such as points, segments, planes, polygons and polyhedrons.
Learning outcomes of the course :  
The aim of this cours is to give the audience the opportunity to have a knowlege of the most usual approaches used to solve certain kind of geometric problems such as :
  • Collision detection
  • Triangulation/Tesselation of a domain (eg. mesh generation algorithms for scientific computing or scientific visualization)
  • Efficient computation of intersection between geometric primitives
  • Nearest neighbor
  • Computation of robust predicates (eg. Is a point located inside a given triangle or not). Robust means here that the result does not depend on small errors due to rounding in floating point arithmetics.
  • The level-sets Method
Prerequisites and co-requisites/ Recommended optional programme components :  
Undergraduate knowlege in algorithmics and geometry
Planned learning activities and teaching methods :  
The practical part of the cours is constituted by some practical exercises and a project where students work in an autonomous manner, in groups of 2. The aim of the practical exercises is that students should implement basic CG algorithms.
Mode of delivery (face-to-face ; distance-learning) :  
To be determined with the professor
Recommended or required readings :  
M. de Berg, O. Cheong, M.van Kreveld, M. Overmars (2008). Computational Geometry (3rd revised edition ed.). Springer-Verlag. ISBN 3-540-77973-6 (Electronic copy available in at the library)
Assessment methods and criteria :  
Project & in-session exercices.
Work placement(s) :  
Organizational remarks :  
The cours is exceptionally streched along the whole academic year.
Contacts :


Bachelors, masters, advanced master et AESS

Lifelong Learning Education

Doctorat (Ph.D.)

Search by teacher

Search by course code and title

Students and Studies Administration - Academic Affairs - Contact : Monique Marcourt, General Director for Education and Training - Developed by SEGI