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. |