Schemat Voronoi na wykresie

Niech będzie wykresem z (dodatnio) ważonymi krawędziami. I chcemy określić schemat Voronoi dla zestawu węzłów / miejsca , do wiązania się z węzła subgraph w indukowanej przez wszystkie węzły ściśle bliżej niż jakiegokolwiek innego węzła , pomiar długości ścieżki za pomocą sumy wag na łukach. jest „s Woronoja obszar . Na przykład zielone węzły poniżej znajdują się w , a żółte węzły w . $G$ $S$ $v \in S$ $R(v)$ $G$ $v$ $S$ $R(v)$ $v$ $R(v_1)$ $R(v_2)$
wprowadź opis zdjęcia tutaj
Chciałbym zrozumieć strukturę diagramu Voronoi. Na początek, jak wygląda schemat dwóch witryn i , tj. Jak wygląda dwusieczny dwumiejscowy (niebieski w powyższym przykładzie)? Sądzę z dwusieczną jako uzupełnienie w . Oto dwa konkretne pytania: $v_1$ $v_2$ $B(v_1,v_2)$ $R(v_1) \cup R(v_2)$ $G$

Pytanie 1 Czy bisektor dwóch stron jest w jakiś sposób połączony?

Q2 Czy wypukły w tym sensie, że zawiera najkrótszą ścieżkę między dowolnymi dwoma węzłami w ? $R(v)$ $R(v)$

Z pewnością zostało to już wcześniej zbadane. Czy ktoś może podać referencje / wskaźniki? Dzięki!

Dodatek do komentarza Suresha:
wprowadź opis zdjęcia tutaj

reference-request graph-theory cg.comp-geom Joseph O'Rourke
źródło

Aby Q1 miało sens, potrzebujesz wyczucia twarzy, prawda? W przeciwnym razie „prawdziwy” dwusiecznik znajduje się na środku krawędzi, a wprowadzenie wierzchołków tuż przed tym punktem i po nim gwarantuje, że dwusiecznik zostanie odłączony. Może zakładając, że wykres jest akordowy, możesz coś udowodnić. Co do Q2: jest to nieprawda nawet dla geodezji w wielokącie z dziurami (lub terenami). Domyślam się, że musisz przyjąć na wykresie coś dość mocnego, aby uzyskać nietrywialną odpowiedź na oba pytania.

Sariel Har-Peled,

Dzięki, Sariel, za te obserwacje. Tak, wygląda na to, że liczyłem na zbyt wiele i być może tylko w specjalnych klasach graficznych pojawią się ładne właściwości strukturalne.

Joseph O'Rourke,

Ach, więc na zwykłej kuli komórka voronoi nie może być większa niż półkula, więc nie masz tego problemu. Ale mój komentarz bardziej ogólnie był taki sam jak Sariel, ponieważ prosisz o wypukłość komórek voronoi w potencjalnie generycznej różnorodności riemannowskiej i to nie powinno być prawdą.

Suresh Venkat,

S

$S$

S

$S$

K_{2, n}

$K_{2, n}$

Więc teraz myślę, że może tu jest interesujące pytanie. Co jeśli podstawowa metryka jest różnorodna (jak sugeruje Suresh). Teraz łączymy dwa punkty wtedy i tylko wtedy, gdy istnieje trzeci punkt q, takie dwa pozostałe punkty są dwoma najbliższymi sąsiadami (pomyśl o tym jako o jakimś kompleksie świadków). Naturalna hipoteza byłaby taka, że jeśli kolektor podwaja się, wówczas zawsze można dodać punkty O (1) w taki sposób, że dwusiecznik jest podłączony. Hmmm ...

Sariel Har-Peled,

Mehlhorn, K .: Szybszy algorytm aproksymacyjny dla problemu Steinera na wykresach. Information Processing Letters 27, 125–128 (1988)

Erwig, M .: Wykres Voronoi z aplikacjami. Networks 36 (3), 156–163 (2000)

oba odniesienia zostały skopiowane z

Matthew T. Dickerson, Michael T. Goodrich, Thomas D. Dickerson, Ying Daisy Zhuo: Diagramy Voronoi w obie strony i podwojenie gęstości w sieciach geograficznych. Transakcje dotyczące obliczeń 14: 211-238 (2011)

David Eppstein
źródło

To zajmie trochę kopania, ale powierzchownie nie wydaje się, że wiele własności strukturalnych diagramu zostało zidentyfikowanych w tych artykułach (być może dlatego, że istnieje kilka ważnych właściwości!).

Joseph O'Rourke,

w rzeczywistości niewiele wiadomo; mamy kolejny lemat lub dwa w sommer.jp/voronoi.htm

Christian Sommer

Schemat Voronoi na wykresie

Odpowiedzi: