Geometric Algorithms – MIRI

Seminars on Innovation and Research in Informatics (MIRI)
Specialization in Computer Graphics and Virtual Reality
Departament de Matemàtica Aplicada II
Facultat d’Informàtica de Barcelona
Universitat Politècnica de Catalunya


This seminar is designed as an introduction to geometric algorithms. As the field is far too wide to fit in a short seminar, a strong selection is been done every year. The proposed contents (and related activities) intend to give:

  • An idea of both the topics and the applications of the field.
  • The most useful algorithmic tools in the field.
  • A selection of topics intended for computer graphics students.


  1. Introductory material
  2. Convex hulls in 2D
  3. Voronoi diagrams and Delaunay triangulations in 2D
  4. Duality and its applications
  5. Convex hulls in 3D
  6. Analyzing randomized incremental algorithms: An introduction
  7. Voronoi diagrams and Delaunay tessellations in 3D or with restrictions
  8. Applying Voronoi diagrams and Delaunay tessellations to shape reconstruction


Computational Geometric Algorithms Library (CGAL)

Never implement a geometric algorithm before checking if CGAL has it! It is a reliable and efficient sofware!

Mathematical text editor

LaTeX is the most extended editor of scientific texts (LaTeX is used to write all the textbooks of scientific publishers as important as Springer, and also most of the mathematics and computer science conferences around the world). It’s a free source software that has versions for all operating systems. You can download LaTeX from

For those of you who work on windows, WinEdt is a very convenient editor for writing LaTeX code. You can download it from


Each person likes preparing his/her figures with his/her favorite drawing program. I use IPE (an evolution of xfig designed by a computational geometer), because it allows me to draw the geometric figures that I need, because it integrates text in LaTeX, and because it allows me to also prepare my presentations in a very easy what-you-see-is-what-you-get way. IPE is free source and has versions for all the operating systems. You can download it from

Geometric constructions

In addition to producing your own drawings, you may whish to create and experiment with geometric constructions. If so, we recommend GeoGebra.

Related events