|
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 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.
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
Montréal, Québec, CANADA, H3A 2A7
Last modified 2002-12-05