Computando distâncias geodésicas com difusão

8

Estou tentando resolver um problema de APSP (caminho mais curto de todos os pares) em um gráfico ponderado. Na verdade, este gráfico é uma grade dimensional de 1, 2 ou 3, e os pesos em cada aresta representam a distância entre seus dois vértices. O que eu quero ter é a distância do gráfico geodésico (caminho mais curto através do gráfico), para cada par de vértices.

Eu quero um método baseado em difusão, porque é mais rápido que um algoritmo Dijkstra ou Floyd-Warshall. Estou tentando conseguir isso usando a equação do calor:

dvocêdt=Δvocê.
No final, meu aplicativo precisa de um kernel do formatoexp(-d2/γ)comda distância geodésica do gráfico.

Minha esperança é que, como a solução deveria ser a função verde de difusão :

você(t,x,y)=(14πt)-dEum2exp(-d2(x,y)4t),

então eu posso usar diretamente essa solução (com alguns ajustes para me livrar do fator à frente) como meu kernel, e o parâmetro γ será ajustado ajustando t .

Ainda não consegui fazer algo que funcione e gostaria de alguma ajuda. Eu tentei muitas coisas até agora e existem vários problemas que surgem. É difícil e demorado explicar todos eles em uma pergunta; portanto, explicarei primeiro o que considero o início de uma boa abordagem e, depois, faça algumas perguntas gerais.


Da mesma forma que é feito na primeira etapa do algoritmo Geodésico no Calor, por Crane et al., Com uma etapa de Euler para trás, eu posso resolver o sistema linear: com t o passo de difusão, matriz laplaciana e Dirac em um dos vértices.

(1)(Eud-teu)você=você0 0
tu 0euvocê0 0

A resolução da equação (1) na verdade fornece um kernel da forma , o que não é desejado. Portanto, eu tenho que fazer K subiterações no tempo e resolver K vezes: que fornece .( I d - texp(-d/γ) u = M - 1 . . . M - 1 u 0

(Eud-tkeu)você=você0 0Mvocê=você0 0
você=M-1...M-1você0 0você=M-Kvocê0 0

À medida que K aumenta, o kernel deve convergir para um quadrado .exp(-d2/γ)


Agora, aqui estão as perguntas:

  • Devo usar um gráfico Laplaciano ou uma diferença finita Laplaciano? AFAIU, um gráfico laplaciano é normalizado para ter 1 na diagonal, enquanto um FE laplaciano tem o grau na diagonal e é multiplicado por1h2

  • Como incorporar os pesos dos gráficos no Laplaciano, para que a distância que recebo na solução seja a distância geodésica do gráfico? Quero poder prever qual será o intervalo de valores de na solução, em relação ao intervalo de pesos e aos parâmetros , e o número de pontos em uma direção (tamanho total do domínio: ).d(x,y)tKnN=ndEum

  • Quais condições de contorno devo usar no Laplaciano? Sinto que não devo impor os valores da função (Dirichlet) na fronteira, porque isso significaria impor a maior distância. Ou devo? Tentei condições homogêneas de Neumann e condições homogêneas de Dircihlet, mas em ambos os casos, recebo alguma distorção perto dos limites da parábola (que verifico calculando o log da solução e subtrair o mínimo).d(x,y)2você(t)

  • Devo usar uma equação de difusão? : , pois a difusão depende espacialmente ?vocêt=(κvocê)

Referências :

Matthieu
fonte
1
Você provavelmente já viu isso, mas, caso contrário, a página da web cs.cmu.edu/~kmcrane/Projects/HeatMethod possui um link para implementações do "método de aquecimento" em alguns idiomas diferentes.
amarney
eu1
exp(-d2gumammuma)
eu1n3
(Eu,j,k)(Eu1,j1,k1)(Eu2,j2,k2)eu1|Eu1-Eu2|+|j1-j2|+|k1-k2|

Respostas:

1

Laplaciano combinatório? Depende do que você espera da sua solução. Algo razoável de se esperar é que sua solução seja independente da maneira como você malha sua superfície (ou o mais independente possível). Se você quiser isso, então claramente um gráfico combinatório Laplaciano não é o que você precisa, pois o resultado seria completamente diferente se você alterar a malha.

T

T={λ1p1+λ2p2+λ3p3 | λ1+λ2+λ3=1;λ10 0;λ20 0;λ30 0}

p1,p2,p3C0 0

Discretizando com o MEFCom esse ponto de vista (FEM clássico), projetando a equação com base em funções lineares por partes (ou outras se desejar), você pode construir uma discretização FEM de sua equação e resolvê-la. Consulte um livro clássico sobre como fazer isso, por exemplo [5] (também disponível na página do autor em arquivos pdf em inglês e francês), que explica completamente a derivação do Laplaciano projetada em funções lineares por partes. Alguns cuidados precisam ser tomados: muitos papéis de computação gráfica misturam a discretização do operador (matriz de rigidez) com o "produto escalar" da base da função usada (matriz de massa), combinando-os em uma única matriz (que eles chamam de " Laplaciano discreto "). Para entender completamente o que está acontecendo, será necessário considerá-los separados,

Teorema e topologia de Varadhan:Algo que precisa ser mencionado sobre o "método do calor" [3] que você cita: é baseado em um teorema provado por Varadhan [1]. O artigo original de Varadhan prova o resultado usando uma parametrização da superfície e "recuando" todos os cálculos no espaço de parâmetros (usando a regra da cadeia). Como usa uma parametrização, a prova é válida apenas para objetos que possuem uma parametrização não degenerada. Em particular, isso impõe que o objeto em consideração seja homeomórfico em um disco. Essa restrição no teorema de Varadhan também é mencionada em [2], página 400: "A fórmula de Varadhan funciona dentro do raio da injetividade, o que acontece quando y se move para o local do corte de x ... mudanças dramáticas ocorrem ... eventos estranhos ocorrem em pontos antipodais ". O 'local de corte' é a zona na qual você colaria um disco toplogical para formar um objeto de topologia arbitrária (ou, de maneira diferente, se você cultivar uma 'célula Voronoi' a partir de um ponto, é aí que o limite da célula Voronoi colidirá automaticamente). Se você quiser usar algo além de um disco topológico, estará por sua conta (sem garantia matemática). No entanto, [3] relata alguns resultados empíricos tendendo a mostrar que o que você obtém é razoável, portanto, para aplicações práticas, ele pode fazer o trabalho. Agora, se você quiser provar teoremas, precisará saber que eles funcionarão apenas para discos topológicos (a menos que você encontre uma maneira de estendê-los para casos mais gerais). Se você quiser usar algo além de um disco topológico, estará por sua conta (sem garantia matemática). No entanto, [3] relata alguns resultados empíricos tendendo a mostrar que o que você obtém é razoável, portanto, para aplicações práticas, ele pode fazer o trabalho. Agora, se você quiser provar teoremas, precisará saber que eles funcionarão apenas para discos topológicos (a menos que você encontre uma maneira de estendê-los para casos mais gerais). Se você quiser usar algo além de um disco topológico, estará por sua conta (sem garantia matemática). No entanto, [3] relata alguns resultados empíricos tendendo a mostrar que o que você obtém é razoável, portanto, para aplicações práticas, ele pode fazer o trabalho. Agora, se você quiser provar teoremas, precisará saber que eles funcionarão apenas para discos topológicos (a menos que você encontre uma maneira de estendê-los para casos mais gerais).

[1] Varadhan 1967, processos de difusão em um pequeno intervalo de tempo, Comm. Matemática pura e aplicada, 20, 659-685

[2] Vista panorâmica da geometria de Riemann, Marcel Berger, Springer, 2003.

[3] Geodésica no calor, K. Crane et al., 2013

[5] https://global.oup.com/academic/product/numerical-analysis-and-optimization-9780199205219?cc=fr&lang=en&

BrunoLevy
fonte
Obrigado por estas guildelines detalhadas! O que você chama de "topologia de disco"? É algo que é homeomórfico para um disco?
matthieu
Sim, é o que eu quis dizer (você está certo, do jeito que você diz que é mais padrão, estou atualizando a resposta).
BrunoLevy