This sounds correct to me. You're definitely right about Delauney graphs and you can get that data from my module by looking at which points correspond to an edge. The problem for me is that I don't know if I can actually translate this solution into code! Maybe I'll give it a try and see what I can come up with.
-sam
Comment on Re^2: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks (Delaunay graph)