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

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 $$$$\Lambda = \{(p_1,p_0) ... (p_{N-2},p_{N-1}), (p_{N-1},p_N) \} \subset E.$$$$

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 $$$$\theta_{i,{i+1}} = cos ^{-1} (\frac{ \vec{ \omega } \cdot \vec{ \nu} }{|\vec{ \omega }| \, |\vec{ \nu}|}) = min\{ \theta_{i,j} \, \forall j \in J \}$$$$

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.

• The question looks very specific but may be known to specialists. My memory told me that I might listened about routing on Delaunay triangulations at “Graph Drawing and Network Visualization” in Athens two years ago. So I googled and found a paper “Upper and Lower Bounds for Competitive Online Routing on Delaunay Triangulations” by Bonichon et. al. I think you can try to ask them. They deal with close problems and may know an answer to yours or be interested in it. – Alex Ravsky Dec 5 '18 at 17:12
• Thank you @AlexRavsky for the suggestion and interesting reference! Actually, I think now that the statement as I have it written is false. The unweighted path between two points can does not have to be the largest angle. However, it seems still (at least for Poisson-Delaunay triangulations) that a weighted path (i.e. considering Euclidean distance of each edge) might still obey the rule... – Entangler Dec 13 '18 at 8:30