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.
I suppose one can move along the edges of the square.
Let us say you want to move from the corner north west to the corner south east. Now imagine all points in the north east corner except one, like this:
This
Now you see if you would follow the green lines from start to your target corner while also using edges of the square when required, the traveled distance would already be quite long. I don't think there is a result about the minimum path length, because it really depends on the distribution of points you have. But at least we have the Triangle inequality...
You could however use existing results on the Complexity of the Voronoi-Diagram (There are quite a bunch of results about this), and somehow use bounds on the number of edges in a Voronoi-Diagram to at least get a result on the expected minimum path length.