A square is divided into convex polygons. Is this always a Voronoi diagram? If not, what are some simple examples of non-Voronoi tilings?
Which of the pentagon tilings are Voronoi?
I took a look at Recognizing Dirichlet tessellations. There are three rules right off:
- At a Voronoi vertex, all angles $a < \pi$.
- Let segment $p q$ be between two trivalent vertices, and let angles $p$ and $q$ be those angles that don't include $p q$. Then $p+q> \pi$.
- If a Voronoi tessellation has more than one vertex, the generating points are uniquely determined.
There are other rules listed, but those three are a powerful start.