Improving shortest paths in the Delaunay triangulation
| Data(s) |
2012
|
|---|---|
| Resumo |
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 u{p} improves as much as possible. We study 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. |
| Formato |
application/pdf |
| Identificador | |
| Idioma(s) |
eng |
| Publicador |
Facultad de Informática (UPM) |
| Relação |
http://oa.upm.es/19280/1/INVE_MEM_2011_121582.pdf http://hdl.handle.net/2117/16981 info:eu-repo/semantics/altIdentifier/doi/null |
| Direitos |
http://creativecommons.org/licenses/by-nc-nd/3.0/es/ info:eu-repo/semantics/openAccess |
| Fonte |
International journal of computational geometry and applications | XIV Spanish Meeting on Computacional Geometry | 27/06/2011 - 30/06/2011 | Alcalá de Henares, Madrid |
| Palavras-Chave | #Informática |
| Tipo |
info:eu-repo/semantics/conferenceObject Ponencia en Congreso o Jornada PeerReviewed |
