Delaunay decomposition

Goal: given a set of points in the plane (resp. in Euclidean 3-dimensional space, or in higher dimensions) one can define a "Delaunay triangulation" of their convex hull, as defined for instance in this wikipedia page. It is a basic tool in computational geometry. The definition involves the positions of the points with respects of circles (resp. spheres). More recently, more exotic types of Delaunay-like decompositions have been proved to exist, where the circles (resp. spheres) are replaced by special kinds of hyperboloids or paraboloids. The main goal of the project is to compute those "exotic" Delaunay triangulations. To achieve this goal, the students involved will be lead to understand relatively simple notions of projective geometry as well as the basic geometry of spaces of constant curvature, and in particular their projective and conformal models.

Schedule: to be determined.

Persons involved: Advised by Jean-Marc Schlenker, NN.

Difficulty level: medium.

Tools: programs in python/sage, use of computational tools to compute and visualize the various types of Delaunay decompositions considered.

Expected results: first, produce a running program to compute the Delaunay decomposition of a set of points in the Euclidean plane or Euclidean space of dimension 3 (or possibly higher). Then, extend this algorithm to the more exotic versions where circles/spheres are replaced by hyperboloids or paraboloids.

FSCT -- University of Luxembourg