Sei ein Graph mit (positiv) gewichteten Kanten. Ich möchte das Voronoi-Diagramm für eine Menge von Knoten / Stellen S definieren , um einem Knoten v ∈ S
den Teilgraphen R ( v ) von G zuzuordnen, der von allen Knoten induziert wird, die genau näher an v liegen als an jedem anderen Knoten in S , der misst die Länge eines Pfades durch die Summe der Gewichte auf den Bögen.
R ( v ) ist die Voronoi-Region von v . Zum Beispiel sind die grünen Knoten unten in R ( v 1 )und die gelben Knoten sind in .
Ich möchte die Struktur des Voronoi-Diagramms verstehen. Wie sieht zunächst das Diagramm der beiden Stellen v 1 und v 2 aus, dh wie sieht die Halbierende mit zwei Stellen aus (im obigen Beispiel blau)? Ich denke an die Winkelhalbierende B ( v 1 , v 2 ) als das Komplement von R ( v 1 ) ∪ R ( V 2 )
in G . Hier sind zwei spezifische Fragen:
Q1. Ist die Halbierende zweier Standorte in gewissem Sinne miteinander verbunden?
Q2. Ist konvex in dem Sinne, dass es den kürzesten Weg zwischen zwei beliebigen Knoten in R ( v ) enthält ?
Sicher wurde dies schon einmal untersucht. Kann jemand Referenzen / Hinweise geben? Vielen Dank!
Nachtrag zu Sureshs Kommentar:
quelle
Antworten:
Mehlhorn, K.: Ein schnellerer Approximationsalgorithmus für das Steiner-Problem in Graphen. Information Processing Letters 27, 125–128 (1988)
Erwig, M.: Das Diagramm Voronoi-Diagramm mit Anwendungen. Networks 36 (3), 156–163 (2000)
beide Referenzen kopiert von
Matthew T. Dickerson, Michael T. Goodrich, Thomas D. Dickerson und Ying Daisy Zhuo: Voronoi-Runddiagramme und Verdoppelung der Dichte in geografischen Netzwerken. Transactions on Computational Science 14: 211 & ndash; 238 (2011)
quelle