Improving shortest paths in the Delaunay triangulation

Hernández Peñalver, Gregorio and Abellanas Oar, Manuel and Claverol, Merce and Hurtado Díaz, Fernando Alfredo and Sacristán Adinolfi, Vera and Saumell Mendiola, Maria and Silveira, Rodrigo Ignacio (2012). Improving shortest paths in the Delaunay triangulation. In: "XIV Spanish Meeting on Computacional Geometry", 27/06/2011 - 30/06/2011, Alcalá de Henares, Madrid. ISBN 0218-1959. pp. 117-120.

Description

Title: Improving shortest paths in the Delaunay triangulation
Author/s:
  • Hernández Peñalver, Gregorio
  • Abellanas Oar, Manuel
  • Claverol, Merce
  • Hurtado Díaz, Fernando Alfredo
  • Sacristán Adinolfi, Vera
  • Saumell Mendiola, Maria
  • Silveira, Rodrigo Ignacio
Item Type: Presentation at Congress or Conference (Article)
Event Title: XIV Spanish Meeting on Computacional Geometry
Event Dates: 27/06/2011 - 30/06/2011
Event Location: Alcalá de Henares, Madrid
Title of Book: International journal of computational geometry and applications
Date: 2012
ISBN: 0218-1959
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Matemática Aplicada
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (685kB) | Preview

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 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.

More information

Item ID: 19280
DC Identifier: http://oa.upm.es/19280/
OAI Identifier: oai:oa.upm.es:19280
Official URL: http://hdl.handle.net/2117/16981
Deposited by: Memoria Investigacion
Deposited on: 24 Sep 2013 17:33
Last Modified: 21 Apr 2016 17:32
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM