Diagrama de Voronoi em um gráfico

Seja um gráfico com arestas ponderadas (positivamente). Quero definir o diagrama de Voronoi para um conjunto de nós / sites , para associar a um nó o subgrafo de induzido por todos os nós estritamente mais próximos de do que qualquer outro nó em , medindo o comprimento de um caminho pela soma dos pesos nos arcos. é a região de Voronoi de . Por exemplo, os nós verdes abaixo estão em e os nós amarelos estão em . $G$ $S$ $v \in S$ $R(v)$ $G$ $v$ $S$ $R(v)$ $v$ $R(v_1)$ $R(v_2)$
insira a descrição da imagem aqui
Eu gostaria de entender a estrutura do diagrama de Voronoi. Para começar, como é o diagrama dos dois sites e , ou seja, como é a bissetor de dois sites (azul no exemplo acima)? Eu penso da bissectriz como o complemento de em . Aqui estão duas perguntas específicas: $v_1$ $v_2$ $B(v_1,v_2)$ $R(v_1) \cup R(v_2)$ $G$

Q1 A bissetriz de dois sites está conectada em algum sentido?

Q2 É convexo no sentido de que ele contém o caminho mais curto entre dois nós em ? $R(v)$ $R(v)$

Certamente isso já foi estudado antes. Alguém pode fornecer referências / indicadores? Obrigado!

Adendo ao comentário de Suresh:
insira a descrição da imagem aqui

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

Para o Q1 fazer sentido, você precisa de um senso de rostos, certo? Caso contrário, a bissetriz "real" fica no meio das arestas e a introdução de vértices antes e depois desse ponto garante que a bissetriz esteja desconectada. Talvez se você assumir que o gráfico é cordial, você pode provar alguma coisa. Quanto ao Q2: isso é falso mesmo para geodésicos em um polígono com furos (ou terrenos). Meu palpite seria que você precisa assumir algo bastante forte no gráfico para obter uma resposta não trivial às duas perguntas.

Sariel Har-Peled

Obrigado, Sariel, por essas observações. Sim, parece que eu estava esperando demais, e talvez apenas em classes especiais de gráficos haja boas propriedades estruturais.

Joseph O'Rourke

ah, na esfera regular, uma célula voronoi não pode ficar maior que um hemisfério, então você não tem esse problema. Mas meu comentário mais geralmente foi o mesmo de Sariel, pois você está pedindo a convexidade de células voronoi em uma variedade riemanniana potencialmente genérica e isso não deve ser verdade.

Suresh Venkat

S

$S$

S

$S$

K_{2, n}

$K_{2, n}$

Então agora estou pensando que talvez haja uma pergunta interessante aqui. E se a métrica subjacente for uma variedade (como sugerido por Suresh). Agora, conectamos dois pontos se, e somente se, existe um terceiro ponto q, como os outros dois pontos são os dois vizinhos mais próximos (pense nisso como uma espécie de complexo de testemunhas). Uma conjectura natural seria que, se o coletor estiver dobrando, sempre será possível adicionar pontos O (1) de modo que a bissetriz esteja conectada. Hmmm ...

Sariel Har-Peled

Mehlhorn, K .: Um algoritmo de aproximação mais rápido para o problema de Steiner em gráficos. Cartas de processamento de informações 27, 125–128 (1988)

Erwig, M .: O gráfico do diagrama de Voronoi com aplicações. Redes 36 (3), 156-163 (2000)

ambas as referências copiadas de

Matthew T. Dickerson, Michael T. Goodrich, Thomas D. Dickerson, Ying Daisy Zhuo: Diagramas de Voronoi de ida e volta e densidade de duplicação em redes geográficas. Transactions on Computational Science 14: 211-238 (2011)

David Eppstein
fonte

Isso exigirá alguma escavação, mas superficialmente, não parece que muitas propriedades estruturais do diagrama tenham sido identificadas nesses documentos (talvez porque existam poucas propriedades dignas de nota!).

Joseph O'Rourke

de fato, pouco parece ser conhecido; nós temos um outro lema ou dois em sommer.jp/voronoi.htm

Christian Sommer

Diagrama de Voronoi em um gráfico

Respostas: