Algoritmos em gráficos geométricos aleatórios

Um gráfico geométrico aleatório ( https://en.wikipedia.org/wiki/Random_geometric_graph ) é construído escolhendo pontos em aleatoriamente, de acordo com alguma distribuição, e definindo se , para alguns parâmetros r . Gráficos geométricos são úteis na modelagem de redes do mundo real.$n$$\mathbb{R}^d$$p_i \sim p_j$$\|p_i - p_j\|<r$$r$

Por exemplo, podemos modelar um mapa de transporte usando a distribuição uniforme em $[0,1]^2$ .

Estou interessado em saber se existem bons algoritmos teóricos para lidar com esses gráficos. Por exemplo, existe um algoritmo para encontrar o caminho mais curto entre dois vértices que é melhor (em expectativa) para esses gráficos do que o BFS? Obviamente, esse algoritmo seria útil para os fabricantes de GPS.

Pesquisa como esta existe?

Os gráficos que você recebe são conhecidos como gráficos de disco unitário . Existe uma vasta literatura sobre algoritmos em gráficos de disco unitário. Como você está perguntando sobre os caminhos mais curtos, consulte este artigo de Cabello e Jejcic . Obviamente, tudo isso não levará em consideração que os gráficos são gerados por algum processo aleatório.

Para referências adicionais, consulte a página da Wikipedia ou o artigo de Cabello e Jejcic.