I computed a Voronoï diagram from a set of point (with Boost.polygon).
I try to find a Delaunay triangulation, connecting each cell center for each Voronoï edge, but I miss some edges.
In the following image, the red dots are my initial points, the blue lines are the Voronoï edges (I ignored infinite edges), and the green lines are the triangulation edges (on green edge for each blue edge, connecting two cell origins).
We can see that diagonal edges are missing. What am I missing?
Here are more examples:
When a vertex in a Voronoi diagram has valence greater than three (sometimes four in your examples) the Delaunay triangles aren't triangles (quadrilaterals in the examples).
The second example shows how a small perturbation can turn a four-valent vertex into two close together three-valent vertices. Then there's a short segment joining them that has an honest perpendicular to connect two of the original points. In the quadrilateral case, neither diagonal is the correct one.
If you choose centers at random in the plane then all vertices will have valence three with probability 1.
There may be conventions in the definitions about whether the "missing" diagonals should be considered when the rare coincidences happen, and your software thinks not. (I haven't looked at the software, and last thought about Voronoi diagrams years ago.)