The study of fundamental discrete geometric structures such as convex polyhedra, Voronoi diagrams or Delaunay triangulations is one of the central subjects of algorithmic geometry. A useful correspondence is established between Voronoi diagrams, Delaunay triangulations and convex polyhedra. McMullen's theorem, which increases the number of faces of a convex polyhedron, is used to limit the Combinatorics complexity of Voronoi diagrams and Delaunay triangulations.
In addition to analyzing geometric structures, the aim of algorithmic geometry is to design algorithms to build these structures and represent them in the form of computer programs. The lecture presents a first simple algorithm for constructing the convex envelope of a finite set of points in a space of any dimension. Similar results can be deduced for Voronoi diagrams and Delaunay triangulations, and allow us to address related questions such as the calculation of a ball union or Voronoi diagrams for different metrics.
