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 .

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 < minv (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 c1 and c2 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 c1 and c2.

• 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 2|V| - 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élix-Olivier Duguay

School of Computer Science, McGill University

3480 University St., Suite 124