Abstract
The detour and spanning ratio of a graph G embedded in \(\mathbb{E}^{d}\) measure how well G approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe O(nlog n) time algorithms for computing the detour and spanning ratio of a planar polygonal path. By generalizing these algorithms, we obtain O(nlog 2 n)-time algorithms for computing the detour or spanning ratio of planar trees and cycles. Finally, we develop subquadratic algorithms for computing the detour and spanning ratio for paths, cycles, and trees embedded in \(\mathbb{E}^{3}\) , and show that computing the detour in \(\mathbb{E}^{3}\) is at least as hard as Hopcroft’s problem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Advances in Discrete and Computational Geometry. Contemporary Mathematics, vol. 223, pp. 1–56. American Mathematical Society, Providence (1999)
Agarwal, P.K., Klein, R., Knauer, C., Sharir, M.: Computing the detour of polygonal curves. Technical Report B 02-03, Freie Universität Berlin, Fachbereich Mathematik und Informatik (2002)
Agarwal, P.K., Sharir, M., Toledo, S.: Applications of parametric searching in geometric optimization. J. Algorithms 17, 292–318 (1994)
Aichholzer, O., Aurenhammer, F., Icking, C., Klein, R., Langetepe, E., Rote, G.: Generalized self-approaching curves. Discrete Appl. Math. 109, 3–24 (2001)
Alt, H., Guibas, L.J.: Discrete geometric shapes: Matching, interpolation, and approximation. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 121–153. Elsevier, Amsterdam (2000)
Alt, H., Knauer, C., Wenk, C.: Comparison of distance measures for planar curves. Algorithmica 38, 45–58 (2004)
Aurenhammer, F., Klein, R.: Voronoi diagrams. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 201–290. Elsevier, Amsterdam (2000)
Bose, P., Morin, P.: Competitive online routing in geometric graphs. Theor. Comput. Sci. 324, 273–288 (2004)
Chan, T.M.: Geometric applications of a randomized optimization technique. Discrete Comput. Geom. 22(4), 547–567 (1999)
Ebbers-Baumann, A., Klein, R., Langetepe, E., Lingas, A.: A fast algorithm for approximating the detour of a polygonal chain. Comput. Geom. Theory Appl. 27, 123–134 (2004)
Edelsbrunner, H., Guibas, L.J., Sharir, M.: The complexity and construction of many faces in arrangements of lines and of segments. Discrete Comput. Geom. 5, 161–196 (1990)
Erickson, J.: New lower bounds for Hopcroft’s problem. Discrete Comput. Geom. 16, 389–418 (1996)
Fortune, S.J.: A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153–174 (1987)
Grüne, A.: Umwege in Polygonen. Master’s thesis, Institut für Informatik I, Universität Bonn (2002)
Guibas, L.J., Sharir, M., Sifrony, S.: On the general motion planning problem with two degrees of freedom. Discrete Comput. Geom. 4, 491–521 (1989)
Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2, 127–151 (1987)
Icking, C., Klein, R.: Searching for the kernel of a polygon: a competitive strategy. In: Proceedings of the 11th Annual Symposium on Computational Geometry, pp. 258–266 (1995)
Icking, C., Klein, R., Langetepe, E.: Self-approaching curves. Math. Proc. Camb. Philos. Soc. 125, 441–453 (1999)
Koltun, V.: Almost tight upper bounds for vertical decompositions in four dimensions. J. ACM 51, 699–730 (2004)
Langerman, S., Morin, P., Soss, M.: Computing the maximum detour and spanning ratio of planar chains, trees and cycles. In: Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002). Lecture Notes in Computer Science, vol. 2285, pp. 250–261. Springer, Berlin (2002)
Matoušek, J.: Range searching with efficient hierarchical cuttings. Discrete Comput. Geom. 10(2), 157–182 (1993)
Megiddo, N.: Applying parallel computation algorithms in the design of serial algorithms. J. ACM 30(4), 852–865 (1983)
Narasimhan, G., Smid, M.: Approximating the stretch factor of Euclidean graphs. SIAM J. Comput. 30(3), 978–989 (2000)
Rote, G.: Curves with increasing chords. Math. Proc. Camb. Philos. Soc. 115, 1–12 (1994)
Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was partly funded by CRM, FCAR, MITACS, and NSERC. P.A. was supported by NSF under grants CCR-00-86013 EIA-99-72879, EIA-01-31905, and CCR-02-04118, by ARO grants W911NF-04-1-0278 and DAAD19-03-1-0352, and by a grant from the U.S.-Israeli Binational Science Foundation. R.K. was supported by DFG grant Kl 655/14-1. M.S. was supported by NSF Grants CCR-97-32101 and CCR-00-98246, by a grant from the U.S.-Israeli Binational Science Foundation (jointly with P.A.), by a grant from the Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University.
Some of these results have appeared in a preliminary form in [2, 20].
Rights and permissions
About this article
Cite this article
Agarwal, P.K., Klein, R., Knauer, C. et al. Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D. Discrete Comput Geom 39, 17–37 (2008). https://doi.org/10.1007/s00454-007-9019-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-007-9019-9