2
$\begingroup$

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

$\endgroup$

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.