Diagrama de Voronoi en un gráfico

Deje que sea un gráfico con aristas ponderadas (positivamente). Quiero definir el diagrama de Voronoi para un conjunto de nodos / sitios , para asociar con un nodo el subgrafo de inducido por todos los nodos estrictamente más cercanos a que a cualquier otro nodo en , midiendo la longitud de un camino por la suma de pesos en los arcos. es la región de Voronoi de . Por ejemplo, los nodos verdes a continuación están en , y los nodos amarillos están en . $G$ $S$ $v \in S$ $R(v)$ $G$ $v$ $S$ $R(v)$ $v$ $R(v_1)$ $R(v_2)$
ingrese la descripción de la imagen aquí
Me gustaría entender la estructura del diagrama de Voronoi. Para empezar, ¿cómo se ve el diagrama de dos sitios y , es decir, cómo se ve la bisectriz de 2 sitios (azul en el ejemplo anterior)? Pienso en la bisectriz como el complemento de en . Aquí hay dos preguntas específicas: $v_1$ $v_2$ $B(v_1,v_2)$ $R(v_1) \cup R(v_2)$ $G$

Q1. ¿La bisectriz de dos sitios está conectada en algún sentido?

Q2 ¿Es convexo en el sentido de que contiene la ruta más corta entre dos nodos en ? $R(v)$ $R(v)$

Seguramente esto ha sido estudiado antes. ¿Alguien puede proporcionar referencias / punteros? ¡Gracias!

Anexo para el comentario de Suresh:
ingrese la descripción de la imagen aquí

reference-request graph-theory cg.comp-geom Joseph O'Rourke
fuente

Para que Q1 tenga sentido, necesitas algo de sentido de las caras, ¿verdad? De lo contrario, la bisectriz "real" está en el medio de los bordes, e introducir vértices justo antes y después de este punto, garantiza que la bisectriz esté desconectada. Quizás si asumes que el gráfico es cordal puedes probar algo. En cuanto a Q2: esto es falso incluso para geodésicas en un polígono con agujeros (o terrenos). Supongo que debe suponer algo bastante fuerte en el gráfico para obtener una respuesta no trivial a ambas preguntas.

Sariel Har-Peled

Gracias, Sariel, por esas observaciones. Sí, parece que esperaba demasiado, y tal vez solo en clases especiales de gráficos habrá buenas propiedades estructurales.

Joseph O'Rourke

Ah, entonces, en la esfera regular, una célula voronoi no puede crecer más que un hemisferio, por lo que no tiene este problema. Pero mi comentario en general fue el mismo que el de Sariel en el sentido de que usted está pidiendo convexidad de las células voronoi en una variedad riemanniana potencialmente genérica y eso no debería ser cierto.

Suresh Venkat

Para Q1, un contraejemplo más simple es la bisectriz de donde es el lado izquierdo de . La bisectriz está totalmente desconectada.

S

$S$

S

$S$

K_{2, n}

$K_{2, n}$

Josephine Moeller

Así que ahora estoy pensando que quizás haya una pregunta interesante aquí. ¿Qué pasa si la métrica subyacente es múltiple (como lo sugiere Suresh)? Ahora, conectamos dos puntos si y solo si existe un tercer punto q, como los otros dos puntos son los dos vecinos más cercanos (piense en esto como algún tipo de complejo testigo). Una conjetura natural sería que si la variedad se duplica, siempre se pueden agregar O (1) puntos de manera que la bisectriz esté conectada. Hmmm ...

Sariel Har-Peled

Mehlhorn, K .: Un algoritmo de aproximación más rápido para el problema de Steiner en gráficos. Cartas de procesamiento de información 27, 125–128 (1988)

Erwig, M .: El gráfico del diagrama de Voronoi con aplicaciones. Redes 36 (3), 156–163 (2000)

ambas referencias copiadas de

Matthew T. Dickerson, Michael T. Goodrich, Thomas D. Dickerson, Ying Daisy Zhuo: Diagramas de Voronoi de ida y vuelta y densidad de duplicación en redes geográficas. Transactions on Computational Science 14: 211-238 (2011)

David Eppstein
fuente

Esto requerirá algo de investigación, pero superficialmente, no parece que se hayan identificado muchas propiedades estructurales del diagrama en estos documentos (¡quizás porque hay pocas propiedades notables!).

Joseph O'Rourke

de hecho, no parece mucho saberse; tenemos otro lema o dos en sommer.jp/voronoi.htm

Christian Sommer

Diagrama de Voronoi en un gráfico

Respuestas: