|
Maximum Detour and |
|||||||||
|
|
|||||||||
|
|
Maximum Detour and Spanning Ratio |
Index
Vertex of a cone. In the case of these infinite cones, it is the vertex from which the cone originates.
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.
The degree of a vertex is the number of edges that are incident to this vertex.
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.
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]
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.
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.
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]
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.
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.
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.
The sink of a path is it's first vertex.
The source of a path is it's last vertex.
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
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.
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.
A tree is a graph G = (V, E) such that there exist exactly one path in G from any pair of vertices in V.
Next | |
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
Montréal, Québec, CANADA, H3A 2A7
Last modified 2002-12-05