Even then, Euclidean distances and travel paths are easy to calculate on Voronoi diagram. 
Exactly. I did my research. Delauney triangulation and you have all your paths, and they have some nice properties, too (guaranteed to only ever cross exactly one border, guaranteed to be the shortest distance, border guaranteed to be exactly halfway between the origin points, etc. etc.).
Right now, though, I'm stopped because the PHP implementation of Fortune's Algorithm that I use is broken. At more then 16k cells, it takes forever and sometimes goes into an endless loop.
