|
Maximum Detour and Spanning Ratio |
|||||||||
|
Maximum Detour and Spanning Ratio |
References
Algorithm
[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.
Definitions
[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:
| Next | |
|
|
|
|
Maximum Detour and Spanning Ratio |
|||||||||
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