Ordered Delaunay triangulations

57 Views Asked by At

I would like to show that, given n points in the plane $q_1 ... q_n$ such that the distance between $q_0$ and $q_i$ is smaller than or equal to the distance between $q_0$ and $q_j$ for every $i < j$, then the shortest path in any Delaunay triangulation of the given point set between $q_0$ and $q_k$, is $pathlen(q_0, q_k) \leq k$. Here, $pathlen$ is meant to denote shortest path.

I attempt to prove this via induction on $k$ but I struggle to complete the argument.

For the base case, we know that $pathlen(q_0, q_1) = 1$ because the "closest pair property" follows from the "empty circle property". That is, the circle, whose diameter corresponds to the line segment between $q_0$ and $q_1$ cannot contain any other points from the given set of points by definition of the set. Therefore, this line segment is part of every Delaunay triangulation.

I am trying to extend the argument for the step case of the (weak) induction. Assuming that I have already that $pathlen(q_0, q_{k-1}) \leq k-1$, then I have to prove that there is an edge in the triangulation from $q_{k-1}$ to $q_k$ or from $q_0$ to $q_k$. For example, for $k = 2$, I would have to show the existence of an edge between $q_0$ and $q_2$ or between $q_1$ and $q_2$.