Dependencia de escala de la longitud del camino de Voronoi

Question

Considera un cuadrado de tamaño fijo en el espacio euclidiano. Supongamos que el cuadrado ha sido descompuesto en bloques de Voronoi con un cierto área promedio.

Ahora supongamos que solo puedes moverte a lo largo de los bordes del diagrama de Voronoi, y deseas recorrer una cierta distancia en el espacio de incrustación. ¿Existe un resultado sobre cómo depende la longitud mínima de tu camino a lo largo de los bordes de Voronoi de la finura de la descomposición de Voronoi (es decir, del tamaño promedio de los bloques)?

Actualización: Para hacer esto más específico, considera el siguiente ejemplo: Tengo tres descomposiciones de Voronoi de longitud de borde promedio de 0.3, 0.1 y 0.02, y estoy interesado en las longitudes de los caminos rojos, es decir, la longitud mínima esperada del camino. En el ejemplo, los caminos son aproximadamente de la misma longitud, pero no sé si hay una declaración más general conocida. Tengo la sensación de que las celdas más grandes tienen menos desvíos más largos, mientras que las celdas más pequeñas tienen más desvíos más cortos, y los efectos se cancelan, hasta cierto punto.

Supongo una distribución de puntos "razonablemente uniforme", y las celdas de Voronoi son mucho más pequeñas que el cuadrado circundante, por lo que los lados del cuadrado no deberían tener una influencia importante.

Answer 1

Supongo que uno puede moverse a lo largo de los bordes del cuadrado.

Imaginemos que quieres moverte desde la esquina noroeste hasta la esquina sureste. Ahora imagina todos los puntos en la esquina noreste excepto uno, así:

Esto

Ahora, si sigues las líneas verdes desde el inicio hasta tu esquina objetivo, utilizando también los bordes del cuadrado cuando sea necesario, la distancia recorrida ya sería bastante larga. No creo que haya un resultado sobre la longitud mínima de la ruta, porque realmente depende de la distribución de los puntos que tengas. Pero al menos tenemos la desigualdad del triángulo...

Sin embargo, podrías utilizar los resultados existentes sobre la Complejidad del Diagrama de Voronoi (Hay bastantes un montón de resultados sobre esto), y de alguna manera utilizar límites en el número de bordes en un Diagrama de Voronoi para obtener al menos un resultado sobre la longitud mínima esperada del recorrido.