Maximum Detour and
Spanning Ratio

 Maximum Detour and Spanning Ratio

Index

apex

Vertex of a cone. In the case of these infinite cones, it is the vertex from which the cone originates.

bat

The union of an infinity of cones that have as apex the points of an edge in three dimensional space. It can be created by dropping a cone from both vertices at the end of the edge and two planar rectangles glued on the cones' mutual tangents.

degree

The degree of a vertex is the number of edges that are incident to this vertex.

detour

The detour of a pair of points (a, b) of a path P is defined as the ratio of the length of the path from one point to the other ||ab||P on the Euclidean distance between the two point on the plane ||ab||. See an example.

graph

A graph is a pair G = (V, E) of sets satisfying E is a subset of [V]. The elements of V are the vertices of the graph G, the elements of E are its edges. The usual way to picture a graph is by drawing a dot for each vertex and joining two of these dots by a line if the corresponding two vertices form an edge. [7]

maximum detour

The maximum detour is the greatest detour of a graph g. The pair of points that yield the highest detour value can be located anywhere on the graph g: located on a vertex, or incident to an edge.

obscure

An space geometric object o1 is obscured by another object o2 when o2 completely covers o1. The upper envelope of the union of the two objects consists only of parts o2, not of o1.

plane graph

A plane graph is a pair (V, E) of finite sets with the following properties (the elements of V are called vertices, those of E edges):

(i) V is a subset of R2

(ii) Every edge is an arc between two vertices

(iii) Different edges have different sets of endpoints

(iv) The interior of an edge contains no vertex and no point of any other edge [7]

polygonal path

A polygonal path is a finite alternating list of vertices and edges {v0, e0, ..., vi, ei, vi+1, ..., vk}, where ei = (vi, vi+1) and vi = vj implies that i = j.

redundant

An input graph (V, E) is redundant if the topological three-dimentional curve resulting from dropping a cone from every point of the space graph is the same for an input graph (W, F) such that W is a strict subset of V and F is a subset of E.

simple cycle

A simple cycle is a finite alternating list of vertices and edges {v0, e0, ..., vi, ei, vi+1, ..., vk, ek, v0}, where ei = (vi, vi+1) and vi = vj implies that i = j. The first and the last vertices of the list are the same vertex.

sink

The sink of a path is it's first vertex.

source

The source of a path is it's last vertex.

space graph

A space graph is a pair (V, E) of finite sets with the following properties (the elements of V are called vertices, those of E edges):

(i) V is a subset of R3

(ii) Every edge is an arc between two vertices

(iii) Different edges have different sets of endpoints

(iv) The interior of an edge contains no vertex and no point of any other edge

span angle

The span angle of a cone is the vertex angle of the largest isosceles triangle that can be created by cutting the cone in half starting at it's apex.

spanning ratio

The spanning ratio, or stretch factor, is the greatest detour of a graph g. The pair of points that yield the highest detour value must be located on the vertices of the graph g.

tree

A tree is a graph G = (V, E) such that there exist exactly one path in G from any pair of vertices in V.

 Previous Next Applet References

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