TY - MGZN
AU - Claverol, M.
AU - Hernández-Peñalver, G.
AU - Hurtado, F.
AU - Sacristán, V.
AU - Saumell, M.
AU - Silveira, R.
AU - Abellanas Oar, Manuel
T2 - International journal of computational geometry and applications
Y1 - 2012
VL - 22
IS - 6
SP - 559
EP - 576
DO - 10.1142/S0218195912500161
UR - http://hdl.handle.net/2117/16981
AB - We study a problem about shortest paths in Delaunay triangulations. Given two nodes s, t in the Delaunay triangulation of a point set S, we look for a new point p ¿ S that can be added, such that the shortest path from s to t, in the Delaunay triangulation of S¿{p}, improves as much as possible. We study several properties of the problem, and give efficient algorithms to find such a point when the graph-distance used is Euclidean and for the link-distance. Several other variations of the problem are also discussed.
AB - We study a problem about shortest paths in Delaunay triangulations. Given two nodes s, t in the Delaunay triangulation of a point set P, we look for a new point p that can be added, such that the shortest 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 algorithms 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.
TI - Improving shortest paths in the Delaunay triangulation
ER -