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: enter image description here 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.

  • $\begingroup$ Can you expand on the question? What do you mean by "minimum path length"? Perhaps the shortest segment on the edge associated with the same Voronoi cell? $\endgroup$ – mlc Mar 26 '17 at 17:25
  • $\begingroup$ By minimum path length I mean the shortest path along sevetal cells. Say the tesselated square is the unit square, the I'm interested in the path from e.g. the left edge ($x=0$) to the right one ($x=1$). I have a feeling it does not depend on the Voronoi size, but actually I don't know. $\endgroup$ – Toffomat Mar 27 '17 at 13:50
  • $\begingroup$ If you are inside a cell, how do you get to the edge? Perhaps you should offer more details and make your question specific. $\endgroup$ – mlc Mar 27 '17 at 14:08

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:


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.