Voronoi Diagramms of Linesegments

Algorithms which compute the Voronoi-Diagram of Points are well known and there are many attempts how to make implementations consistent and effective. A newer problem is to deal with generator sets containing points and line-segments. This yields to much more complex bisectors and distance calculations. An implementation which computes voronoi-diagrams of line-segments has been written by Burnikel, Mehlhorn, Schirra at MPI Saarbrücken. It's based on the randomized incremental algorithm by Klein, Mehlhorn, Meiser.

If you are interested in an introduction, you may read my elaboration.


Implementierung Geometrischer Algorithmen. Sum.Sem.1995, IFI WWU Münster.