Abstract
Let G be an embedded planar graph whose edges may be curves. The detour between two points, p and q (on edges or vertices) of G, is the ratio between the shortest path in G between p and q and their Euclidean distance. The supremum over all pairs of points of all these ratios is called the geometric dilation of G. Our research is motivated by the problem of designing graphs of low dilation. We provide a characterization of closed curves of constant halving distance (i.e., curves for which all chords dividing the curve length in half are of constant length) which are useful in this context. We then relate the halving distance of curves to other geometric quantities such as area and width. Among others, this enables us to derive a new upper bound on the geometric dilation of closed curves, as a function of D/w, where D and w are the diameter and width, respectively. We further give lower bounds on the geometric dilation of polygons with n sides as a function of n. Our bounds are tight for centrally symmetric convex polygons.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abrams, A., Cantarella, J., Fu, J., Ghomi, M., Howard, R.: Circles minimize most knot energies. Topology 42(2), 381–394 (2002)
Chakerian, G.D., Groemer, H.: Convex bodies of constant width. Convexity and its Applications, 49–96 (1983)
Croft, H.P., Falconer, K.J., Guy, R.K.: Unsolved Problems in Geometry. Springer, Heidelberg (1991)
Dumitrescu, A., Grüne, A., Rote, G.: On the geometric dilation of curves and point sets. Preprint (July 2004)
Ebbers-Baumann, A., Grüne, A., Klein, R.: On the geometric dilation of finite point sets. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 250–259. Springer, Heidelberg (2003)
Ebbers-Baumann, A., Grüne, A., Klein, R.: Geometric dilation of closed planar curves: New lower bounds. In: Special issue of CGTA dedicated to Euro-CG 2004 (2004) (to appear)
Gromov, M., Lafontaine, J., Pansu, P.: Structures métriques pour les variétés riemanniennes. In: Textes math., CEDIC / Fernand Nathan, Paris, vol. 1 (1981)
Kubota, T.: Einige Ungleichheitsbeziehungen über Eilinien und Eiflächen. Sci. Rep. Tǒhoku Univ. 12, 45–65 (1923)
Kusner, R.B., Sullivan, J.M.: On distortion and thickness of knots. In: Whittington, S.G., Sumners, D.W., Lodge, T. (eds.) Topology and Geometry in Polymer Science. IMA Volumes in Math. and its Applications, vol. 103, pp. 67–78. Springer, Heidelberg (1998)
Scott, P.R., Awyong, P.W.: Inequalities for convex sets. Journal of Inequalities in Pure and Applied Mathematics, 1(1) (2000), http://jipam.vu.edu.au/article.php?sid=99
Yaglom, I.M., Boltyanski, V.G.: Convex Figures. English Translation, Holt, Rinehart and Winston, New York (1961)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dumitrescu, A., Ebbers-Baumann, A., Grüne, A., Klein, R., Rote, G. (2005). On Geometric Dilation and Halving Chords. In: Dehne, F., López-Ortiz, A., Sack, JR. (eds) Algorithms and Data Structures. WADS 2005. Lecture Notes in Computer Science, vol 3608. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11534273_22
Download citation
DOI: https://doi.org/10.1007/11534273_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28101-6
Online ISBN: 978-3-540-31711-1
eBook Packages: Computer ScienceComputer Science (R0)