On the farthest-segment Voronoi diagram: predicates and robust computation

The Voronoi diagram is a versatile space partitioning structure with numerous applications in diverse areas of science and engineering. The basic concept is simple: given n simple geometric objects in a space, called sites, their Voronoi diagram divides the space into regions such that the Voronoi region of a site s is the locus of points closer to s than to any other site.

In this project we will focus on the farthest Voronoi diagram of line segments and lines in the plane. It is well known that the farthest-segment Voronoi diagram has a tree structure of complexity linear in the number of the input segments. We want to study the algorithmic predicates involved in computing this diagram robustly. If successful this project may lead to a new package in CGAL - the Computational Geometry Algorithms Library, https://www.cgal.org. The project, however, will focus on the construction algorithm and its predicates.

The ideal candidate must have good programming skills, good algorithmic skills, and an interest in geometric computing. Some mathematical skills are also a plus.

More information about the algorithm and robust computation.