Back to Search
Start Over
On the Geometric Dilation of Finite Point Sets
On the Geometric Dilation of Finite Point Sets
- 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