 | |
| INFO2046-1 | Computational Geometry
 |
|
| Duration : | 30h Th, 30h Pr |
|
| Credits/ECTS : |
| Master in Aerospatial Engineering, in-depth approach, 2nd year | | Toute l'année | | 5 |
|
| Master in Computer Engineering, in-depth approach, 2nd year | | Toute l'année | | 5 |
|
| Master in Computer science, Research Focus, 2nd year | | Toute l'année | | 6 |
|
| Master in Mechanical Engineering, in-depth approach, 2nd year | | Toute l'année | | 5 |
|
| Master in Engineering Physics, in-depth approach, 2nd year | | Toute l'année | | 5 |
|
|
|
| Holder(s) : | Eric Béchet |
|
| Language : | French 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. |
|
| Course objective : | 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 : | Undergraduate knowlege in algorithmics and geometry |
|
| Workshops : | The practical part of the cours is constituted by some practical exercises under the supervision of the staff, and a project where students work in an autonomous manner, in groups of 2. The aim of the practical exercises is twofold : on one hand the students should be able to implement basin CG algorithms, on the other hand, they should get acquainted with an existing library : CGAL. |
|
| Organization : | To be determined with the professor |
|
| Written notes : | 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 : | Project & final exam. |
|
| Contacts : | eric.bechet@ulg.ac.be |
|
| Remarks : | The cours is exceptionally streched along the whole academic year. |
|
|
| |
