Loading...
Loading...

Go to the content (press return)

Improving shortest paths in the Delaunay triangulation

Author
Claverol, M.; Hernández-Peñalver, G.; Hurtado, F.; Sacristán, V.; Saumell, M.; Silveira, R.; Abellanas Oar, Manuel
Type of activity
Journal article
Journal
International journal of computational geometry and applications
Date of publication
2012
Volume
22
Number
6
First page
559
Last page
576
DOI
https://doi.org/10.1142/S0218195912500161 Open in new window
Project funding
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
Repository
http://hdl.handle.net/2117/16981 Open in new window
Abstract
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...
Citation
Abellanas, M. [et al.]. Improving shortest paths in the Delaunay triangulation. "International journal of computational geometry and applications", 2012.
Keywords
Delaunay triangulation, Shortest path, dilation
Group of research
CGA -Computational Geometry and Applications
DCG - Discrete and Combinatorial Geometry

Participants

Attachments