Improving shortest paths in the Delaunay triangulation ∗

We study a problem about shortest paths in Delau-nay triangulations. Given two nodes s; t in the De-launay triangulation of a point set P, we look for a new point p that can be added, such that the short-est path from s to t, in the Delaunay triangulation of P ∪ {p}, improves as much as possible. We study several properties of the problem, and give efficient al-gorithms to find such point when the graph-distance used is Euclidean and for the link-distance. Several other variations of the problem are also discussed.