is indeed the correct Voronoi diagram of line segments?
Here the challenge is to write a checking procedure that
is very simple to implement but cannot be fooled by
any incorrect candidate graph. In this talk I present
such a Voronoi checker that needs only linear time.
The most interesting part of the checker is to show the
planarity of the alleged embedding. Here the key quantity
is the winding number of a face cycle in the candidate
graph. Our techniques can be generalized to every type
of diagram where the faces are convex or star-shaped.