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

Introduction                

               Algorithm

 
 


Maximum Detour and
Spanning Ratio

Submit a bug or feature
 

 

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

fdugua@cs.mcgill.ca

 

Last modified 2002-12-05