Maximum Detour and
Spanning Ratio


Maximum Detour and Spanning Ratio








[1] S. Langerman, P. Morin, M. Soss. Computing the maximum detour and spanning ratio of planar chains, trees and cycles. Proceedings of the Nineteenth International Symposium on Theoretical Aspects of Computer Science (STACS), 2002 (to appear).


Other Exact Algorithm

[2] P. K. Agarwal, R. Klein, C. Knauer, and M. Sharir.  Computing the detour of polygonal curves.  Unpublished Manuscript, November 2001.



Approximation Algorithms

O(n log n) (1-Є) approximative for path-cycle-tree

[3] G. Narasimhan and M. Smid.  Approximating the stretch factor of Euclidean graphs. SIAM Journal on Computing, 30(3):978-989, 2001.



O( (n/Є)  log n)   (1-Є) approximative

[4] A. Ebbers-Baumann, R. Klein, E. Langetepe, and A. Lingas. A fast algorithm for approximating the detour of a polygonal chain.  Proceedings of the 9th Annual European Symposium on Algorithms, 1(4):301-358, 1980.



Randomized Reduction

[5] T. M. Chan.  Geometric applications of a randomized optimization technique.  Discrete & Computational Geometry, 22(4):547-567, 1999.



Insertion and Deletion of Arcs

[6] S. J. Fortune.  A sweepline algorithm for Voronoi diagrams.  Algorithmica, 2:153-174, 1987.




[7] R. Diestel. Graph Theory.  Springer-Verlag New York, Inc. 1997.



Applet source code was a modified version of the code from this book:

Computational Geometry in C (2nd Ed.).  Cambridge University Press, September 1998.


The 3D applet was created using source code from The Java(TM) Boutique.



HTML presentation was inspired from Sun's Java documentation pages.



Java source code:









Maximum Detour and
Spanning Ratio

Submit a bug or feature


This page was created as a learning tool in Computational Geometry. It should not be reproduced without the consent of its author.

Félix-Olivier Duguay

School of Computer Science, McGill University

3480 University St., Suite 124

Montréal, Québec, CANADA, H3A 2A7


Last modified 2002-12-05