Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Improving shortest paths in the Delaunay triangulation

Autor
Claverol, M.; Hernández-Peñalver, G.; Hurtado, F.; Sacristán, V.; Saumell, M.; Silveira, R.I.; Abellanas, M.
Tipus d'activitat
Article en revista
Revista
International journal of computational geometry and applications
Data de publicació
2012
Volum
22
Número
6
Pàgina inicial
559
Pàgina final
576
DOI
https://doi.org/10.1142/S0218195912500161 Obrir en finestra nova
Projecte finançador
EUI-EURC-2011-4306 -PUNTOS Y GRAFOS: PUENTES GEOMÉTRICOS (IP04 en CRP Comb. of points sets, ComPoSe, EuroGIGA ESF)
EUROGIGA NR 13604 -CRP ComPoSe: Fonds National de la Recherche Scientique (F.R.S.-FNRS)
GIG/11/E023-GraDR EUROGIGA
Gen. Cat. DGR 2009SGR1040
MTM2008-05043
MTM2009-07242
MTM2012-30951 - MORFOLOGIA GEOMETRICA COMPUTACIO
PIEF-GA-2009-251235
Repositori
http://hdl.handle.net/2117/16981 Obrir en finestra nova
Resum
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 a...
Citació
Abellanas, M. [et al.]. Improving shortest paths in the Delaunay triangulation. "International journal of computational geometry and applications", 2012.
Paraules clau
Delaunay triangulation, Shortest path, dilation
Grup de recerca
CGA -Computational Geometry and Applications
DCG - Discrete and Combinatorial Geometry

Participants

Arxius