3D and Computational Geometry Algorithms

Course Code : IR375

Time Hours : 18 hours

Time Periods : not available yet

Lecturers :

Marc-Pierrot Desseilligny, Research Director, marc.pierrot-deseilligny[at]ign.fr

Florence Cloppet, Assistant Professor, florence.cloppet[at]parisdescartes.fr


Computational Geometry emerged in the 1970’s. It can be defined as the study of algorithms and data structures for geometric objects, with a focus on exact algorithms that are asymptotically fast. The content is coupled in 4 main aspects :

  • a brief recall about algorithmic methods (Incremental linear programming, Divide and Conquer, Plane Sweep algorithms) and data structures (Connected edge list, trees, binary search trees, AVL trees) that are useful for computational geometry.
  • Object Modelisation (surface or volumetric modelisation)
  • Geometrical Notions (point, segment, line, polygon, distances, connectivity, convexity …..)
  • Methods for discrete models (discrete geometry) and for continuous models (Voronoï Diagram, Delaunay Triangulation ….)