Back to Search Start Over

On the Geometric Dilation of Finite Point Sets

On the Geometric Dilation of Finite Point Sets

Authors :
Annette Ebbers-Baumann
Rolf Klein
Ansgar Grüne
Source :
Algorithms and Computation ISBN: 9783540206958, ISAAC
Publication Year :
2003
Publisher :
Springer Berlin Heidelberg, 2003.

Abstract

Let G be an embedded planar graph whose edges may be curves. For two arbitrary points of G, we can compare the length of the shortest path in G connecting them against their Euclidean distance. The maximum of all these ratios is called the geometric dilation of G. Given a finite point set, we would like to know the smallest possible dilation of any graph that contains the given points. In this paper we prove that a dilation of 1.678 is always sufficient, and that π/2 = 1.570... is sometimes necessary in order to accommodate a finite set of points.

Details

ISBN :
978-3-540-20695-8
ISBNs :
9783540206958
Database :
OpenAIRE
Journal :
Algorithms and Computation ISBN: 9783540206958, ISAAC
Accession number :
edsair.doi...........e40ba8dd2890c3a810c7686fc0cdae13
Full Text :
https://doi.org/10.1007/978-3-540-24587-2_27