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)

No java support. Browser must have java capacity to run the applet.

 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 v1, v2 Є V such that v1 is contained in the cone, which spans an angle of 2arctan(1/d), under v2.

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 |V|-1 bats will be scanned for redundancy.

 Previous 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élix-Olivier Duguay

School of Computer Science, McGill University

3480 University St., Suite 124