
Maximum Detour and Spanning Ratio 

Maximum Detour and Spanning Ratio 
Algorithm
Preprocessing
• Transform the plane graph in a 3D space graph such that:
(x, y)_{1} maps to (x, y, 0 ) and
(x, y)_{j} maps to (x, y,  ∑_{i=1toj} distance ((x, y)_{i}, (x, y)_{i+1}) )
• Sort every vertex according to its y value.
• Assume that the cones' span angle is 2α.
A plane P will sweep the space. P is always parallel to the x axis and forms an angle of α with the z axis. Position this plane such that it doesn't intersect a cone/bat (at z = 0, y < min_{v} (y)).
• Plane P produces an event every time it hits a vertex, which is when it reaches the beginning or the end of a cone/bat. The sorted list of vertex will act as the event queue. There are n = V events.
Event Processing
• Create a data structure to represent the intersection of the plane P and the space's segments E this database will be named P∩E. Every edge will be stored as a formula representing its position over time. Since every such upper edge has a mutual exclusive x coordinate location, the insertion and removal of these objects can be performed in logarithmic time O(log n).
case of Spanning Ratio:
• The event is a new vertex v:
First check if v is below the curve on P∩E. If it is, the input is redundant, so the answer is determined. If it isn't, add 2 parabolic curves c_{1} and c_{2} to P∩E representing the intersection of the plane P and the cone whose apex is at v.
Create an events at the locations where the neighbour curves will obscure c_{1} and c_{2}.
• The event is a curve c being obscured:
Remove the event associated with c from the data structure P∩E.
case of Maximum Detour:
• We must first modify the queue such that there are two types of event: the beginning and the end of a bat. Since every vertex except the source and the sink are of degree 2, the queue length becomes 2V  2.
• The event is the beginning of a bat:
We check if the input is redundant by verifying if the vertex is under the curve on P∩E. In the case that the test is unconclusive, we add 4 objects to P∩E: 2 parabolic curves, as before, to represent the cone and 2 line segments to model the planar part the bat.
Create an events at the locations where the neighbour curves will obscure any of the new objects.
• The event is the end of a bat:
We must again add 2 curves which correspond to the intersection of the cone dropped under the event vertex and the plane P∩E.
Create an events at the locations where the neighbour curves will obscure any one of the 2 new arcs.
• The event is a curve or segment disappearing from P∩E:
Remove the event associated with this object. If it is a line segment, if either of its endpoints is within a bat in P∩E, the input is redundant.
Next  
Applet 

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