Computando distâncias geodésicas com difusão

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:

$$\frac{du}{dt} = \Delta u.$$ No final, meu aplicativo precisa de um kernel do formato$\exp(-d^2/\gamma)$com$d$a distância geodésica do gráfico.

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

$$u(t,x,y) = \left(\frac{1}{4\pi t}\right)^{-\frac{dim}{2}}\exp\left(\frac{-d^2(x,y)}{4t}\right),$$

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 $\gamma$ 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.

$$(Id - tL)u = u_0 \tag{1}$$ $t$u $L$$u_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 - $\exp(-d/\gamma)$ u = M - 1 . . . M - 1 u

$$(Id - \frac{t}{k}L)u = u_0 \iff Mu = u_0$$ $u = M^{-1}...M^{-1}u_0 \iff u = M^{-K}u_0$

À medida que K aumenta, o kernel deve convergir para um quadrado .$\exp(-d^2/\gamma)$

---

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 por$\frac{1}{h^2}$

• 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)$$t$$K$$n$$N = n^{dim}$

• 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)^2$$u(t)$

• Devo usar uma equação de difusão? : , pois a difusão depende espacialmente ?$\frac{\partial u}{\partial t}=\nabla\cdot\left(\kappa\nabla u\right)$

Referências :

• Crane et al. 2013: Geodésica no calor: uma nova abordagem para calcular a distância com base no fluxo de calor

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 = \{ \lambda_1 p_1 + \lambda_2 p_2 + \lambda_3 p_3\ |\ \lambda_1 + \lambda_2 + \lambda_3 = 1; \lambda_1 \ge 0; \lambda_2 \ge 0; \lambda_3 \ge 0\}$$

$p_1, p_2, p_3$$C^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&