To access the full text documents, please follow this link: http://hdl.handle.net/2117/16981
Title: | Improving shortest paths in the Delaunay triangulation |
---|---|
Author: | Abellanas, Manuel; Claverol Aguas, Mercè; Hernández-Peñalver, Gregorio; Hurtado Díaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria; Silveira, Rodrigo Ignacio |
Other authors: | Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta |
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 are also discussed. |
Subject(s): | -Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria -Geometria integral -Triangulació -Trigonometria -Triangulation |
Rights: | Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
Document type: | Article - Published version Article |
Share: |