Diagramme de Voronoi dans un graphique

Soit un graphique avec des arêtes pondérées (positivement). Je veux définir le diagramme de Voronoi pour un ensemble de nœuds / sites , associer à un nœud le sous-graphe de induit par tous les nœuds strictement plus proche de que de tout autre nœud en , mesurant la longueur d'un chemin par la somme des poids sur les arcs. est la région de Voronoi de . Par exemple, les nœuds verts ci-dessous sont en $G$ $S$ $v \in S$ $R(v)$ $G$ $v$ $S$ $R(v)$ $v$ $R(v_1)$ et les nœuds jaunes sont dans . Je voudrais comprendre la structure du diagramme de Voronoi. Pour commencer, à quoi ressemble le diagramme de deux sites et , c'est-à-dire à quoi ressemble la bissectrice à 2 sites (bleue dans l'exemple ci-dessus)? Je pense que la bissectrice de comme le complément de dans . Voici deux questions spécifiques: $R(v_2)$
entrez la description de l'image ici
$v_1$ $v_2$ $B(v_1,v_2)$ $R(v_1) \cup R(v_2)$ $G$

Q1. La bissectrice de deux sites est-elle connectée dans un certain sens?

Q2. Est convexe dans le sens où il contient le plus court chemin entre deux noeuds quelconques dans ? $R(v)$ $R(v)$

Cela a sûrement été étudié auparavant. Quelqu'un peut-il fournir des références / pointeurs? Merci!

Addendum pour le commentaire de Suresh:
entrez la description de l'image ici

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

Pour que Q1 ait un sens, vous avez besoin d'un certain sens des visages, non? Sinon, la "vraie" bissectrice est au milieu des arêtes, et l'introduction de sommets juste avant et après ce point, garantit que la bissectrice est déconnectée. Peut-être que si vous supposez que le graphique est en accord, vous pouvez prouver quelque chose. Quant au Q2: c'est faux même pour les géodésiques dans un polygone à trous (ou terrains). Je suppose que vous devez supposer quelque chose d'assez fort sur le graphique pour obtenir une réponse non triviale aux deux questions.

Sariel Har-Peled,

Merci, Sariel, pour ces observations. Oui, il semble que j'espérais trop, et peut-être que dans des classes spéciales de graphiques, il y aura de belles propriétés structurelles.

Joseph O'Rourke

ah donc sur la sphère régulière une cellule de voronoi ne peut pas devenir plus grosse qu'un hémisphère, donc vous n'avez pas ce problème. Mais mon commentaire plus généralement était le même que celui de Sariel en ce que vous demandez la convexité des cellules voronoi dans une variété riemannienne potentiellement générique et cela ne devrait pas être vrai.

Suresh Venkat

S

$S$

S

$S$

K_{2, n}

$K_{2, n}$

Alors maintenant, je pense qu'il y a peut-être une question intéressante ici. Et si la métrique sous-jacente est une variété (comme suggéré par Suresh). Maintenant, nous connectons deux points si et seulement s'il existe un troisième point q, tels que les deux autres points sont les deux voisins les plus proches (pensez à cela comme une sorte de complexe témoin). Une conjecture naturelle serait que si le collecteur double, alors on peut toujours ajouter O (1) points de sorte que la bissectrice soit connectée. Hmmm ...

Sariel Har-Peled

Mehlhorn, K.: Un algorithme d'approximation plus rapide pour le problème de Steiner dans les graphiques. Lettres de traitement de l'information 27, 125-128 (1988)

Erwig, M .: Le diagramme graphique de Voronoi avec applications. Réseaux 36 (3), 156–163 (2000)

les deux références copiées de

Matthew T. Dickerson, Michael T. Goodrich, Thomas D. Dickerson, Ying Daisy Zhuo: diagrammes aller-retour de Voronoi et doublement de la densité dans les réseaux géographiques. Transactions on Computational Science 14: 211-238 (2011)

David Eppstein
la source

Cela va prendre un peu de fouille, mais superficiellement, il ne semble pas que de nombreuses propriétés structurelles du diagramme aient été identifiées dans ces articles (peut-être parce qu'il y a peu de propriétés à noter!).

Joseph O'Rourke

en effet, peu de choses semblent être connues; nous avons un autre lemme ou deux dans sommer.jp/voronoi.htm

Christian Sommer

Diagramme de Voronoi dans un graphique

Réponses: