# Algorithms on random geometric graphs

A random geometric graph (https://en.wikipedia.org/wiki/Random_geometric_graph) is constructed by choosing $n$ points in $\mathbb{R}^d$ at random according to some distribution, and setting $p_i \sim p_j$ if $\|p_i - p_j\|<r$, for some parameter $r$. Geometric graphs are of use in modelling real world networks.

For example, we can model a transportation map using the uniform distribution on $[0,1]^2$.

I am interested in whether there are good graph theoretic algorithms for dealing with these graphs. For example, is there an algorithm for finding the shortest path between two vertices that is better (in expectation) for these graphs than BFS? Obviously such an algorithm would be useful for GPS manufacturers.

Does research like this exist?