
Maximum Detour and Spanning Ratio 

Maximum Detour and Spanning Ratio 
Problem Definition
The first operation to perform is to map the 2D plane graph G to a 3D space graph. In order to do so, the x and y coordinates of the 3D graph must remain the same as in the 2D graph. The z value will be set to the negated value of the distance point on the path to the source. The following illustration will demonstrate this preprocessing.
Plane graph path coordinates: (0, 0), (0, 5), (5, 5), (5, 5) 
Space graph path coordinates: (0, 0, 0), (0, 5, 5), (5, 5, 10), (5, 5, 20) 
Spanning Ratio
The problem of comparing the spanning ratio of a graph S(G) with a given value d can be reduced to determining if a set of V infinite cones are redundant. The input is redundant if there exists two vertices v_{1}, v_{2} Є V such that v_{1 }is contained in the cone, which spans an angle of 2arctan(1/d), under v_{2}.
Maximum Detour
The extra difficulty in computing the detour on any pair of point on a graph is that there is an infinity of points. The exhaustive approach of dropping a cone at every point is, thus, out of question. Fortunately, in a graph, the maximum detour is always between a vertex and a point.
We will now consider the union of the infinity of cones dropped under a line. The terminology used for this topological object is a bat. We can proceed similarly as for the spanning ratio, comparing the maximum detour value of the path D(G) with an arbitrary value d. In order to do so, the set of V1 bats will be scanned for redundancy.
Next  
Algorithm 

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élixOlivier Duguay
School of Computer Science, McGill University
3480 University St., Suite 124
Montréal, Québec, CANADA, H3A 2A7
Last modified 20021205