Prove that the shortest path between two points in a Delaunay triangulation minimizes angle at each step.

278 Views Asked by At

Say we have a set of points $p_{k (k \in K)}\in P$ Poisson distributed in a real coordinate plane $X$ residing in ${\rm I\!R}^{2}$ and with Euclidean distance function $d$ and $K$ is a set of indices. The points form a Delaunay triangulation $D = {P, E}$ where E is the set of edges between points that obeys the empty circle property that no circumcircle of any triangle in $D$ has a point of $P$ in its interior.

Let two points $p_0$ and $p_N$ be points in $D$ that are separated by a shortest path geodesic distance of $N$ and we are interested in determining a shortest geodesic path $\Lambda$ between them i.e. a set of edge tuples \begin{equation} \Lambda = \{(p_1,p_0) ... (p_{N-2},p_{N-1}), (p_{N-1},p_N) \} \subset E. \end{equation}

At any step $i$ along the path, $\vec{\omega} = (p_i,p_N)$ is a vector pointing from a current vertex along the shortest path toward the destination $p_N$ and $\vec{\nu} = (p_i,p_{i+1})$ is a vector pointing to a next vertex along the shortest path to $p_N$, and let $\vec{\mu} = (p_i,p_j)$ be the vector pointing to some neighbor $p_{j (j \in J)}$ geodesically adjacent to $p_i$ and $J$ is the set of indices of vertices adjacent to $p_i$.

The angle $\theta_{i,j} = cos ^{-1} ( \frac{ \vec{ \omega } \cdot \vec{ \mu} }{|\vec{ \omega }| \, |\vec{ \mu}|})$ is the angle between the vector from current point to the destination and the vector to neighbor $j$. Can it be shown that \begin{equation} \theta_{i,{i+1}} = cos ^{-1} (\frac{ \vec{ \omega } \cdot \vec{ \nu} }{|\vec{ \omega }| \, |\vec{ \nu}|}) = min\{ \theta_{i,j} \, \forall j \in J \} \end{equation}

i.e. that by minimizing the angle made by vectors extending from the current vertex out to the destination and an adjacent vertex, the next point on the shortest path can be determined.