Consider a square of fixed size in Euclidean space. Assume the square has been decomposed into Voronoi blocks of a certain average area.
Now assume you can only move along the edges of the Voronoi diagram, and you want to cover a certain distance in the embedding space. Is there a result on how your minimum path length along teh Vornoi edges depends of the fineness of the Voronoi decomposition (i.e. on the average size of the blocks)?
Update: To make this more specific, consider the following example: I have three Voronoi decompositions of average edeg length 0.3, 0.1 and 0.02, and I'm interested in the lengths of the red paths, i.e. the expected minimum path length. In the example, the paths are about the same length, but I don't know whether there is a more general statement known. I have a feeling the the larger cells have fewer longer detours, while the smaller cells have more shorter ones, and the effects cancels out, to some extent.
I assume a "reasonably uniform" point distribution, and the Voronoi cells are much smaller that the surrounding square, so the sides of the square should not have a major influence.