Take the lattice $\mathbb{L}^{2}=(\mathbb{Z}^{2},\mathbb{E}^{2})$ with i.i.d. $\text{U}[0,1]$ weights on the edges, and the random variable $D$ giving the maximal transversal deviation of the geodesic path between two points $\mathbf{x},\mathbf{y} \in \mathbb{Z}^{2}$. This is unique, and formed from the minima over all edge-weighted paths between the points.

An example on a proximity graph on random points is shown. The vertical line is the random variable giving the transversal deviation.

What is known about the distribution of $D$?

$T$, the length of the paths, follows the Tracy-Widom distribution in the case where the weights are i.i.d., at least in some settings e.g. on $\mathbb{L}^{2}$. enter image description here

For example, I have this for the case of a the Delaunay triangulation on random points on a torus, where the weights are now the lengths of the edges in Euclidean space:

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.