|
Maximum Detour and Spanning Ratio |
|||||||||
|
Maximum Detour and Spanning Ratio |
Algorithm
Preprocessing
• Transform the plane graph in a 3D space graph such that:
(x, y)1 maps to (x, y, 0 ) and
(x, y)j maps to (x, y, - ∑i=1toj distance ((x, y)i, (x, y)i+1) )
• Sort every vertex according to its y value.
• Assume that the cones' span angle is 2α.
A plane P will sweep the space. P is always parallel to the x axis and forms an angle of α with the z axis. Position this plane such that it doesn't intersect a cone/bat (at z = 0, y < minv (y)).
• Plane P produces an event every time it hits a vertex, which is when it reaches the beginning or the end of a cone/bat. The sorted list of vertex will act as the event queue. There are n = |V| events.
Event Processing
• Create a data structure to represent the intersection of the plane P and the space's segments E this database will be named P∩E. Every edge will be stored as a formula representing its position over time. Since every such upper edge has a mutual exclusive x coordinate location, the insertion and removal of these objects can be performed in logarithmic time O(log n).
case of Spanning Ratio:
• The event is a new vertex v:
First check if v is below the curve on P∩E. If it is, the input is redundant, so the answer is determined. If it isn't, add 2 parabolic curves c1 and c2 to P∩E representing the intersection of the plane P and the cone whose apex is at v.
Create an events at the locations where the neighbour curves will obscure c1 and c2.
• The event is a curve c being obscured:
Remove the event associated with c from the data structure P∩E.
case of Maximum Detour:
• We must first modify the queue such that there are two types of event: the beginning and the end of a bat. Since every vertex except the source and the sink are of degree 2, the queue length becomes 2|V| - 2.
• The event is the beginning of a bat:
We check if the input is redundant by verifying if the vertex is under the curve on P∩E. In the case that the test is unconclusive, we add 4 objects to P∩E: 2 parabolic curves, as before, to represent the cone and 2 line segments to model the planar part the bat.
Create an events at the locations where the neighbour curves will obscure any of the new objects.
• The event is the end of a bat:
We must again add 2 curves which correspond to the intersection of the cone dropped under the event vertex and the plane P∩E.
Create an events at the locations where the neighbour curves will obscure any one of the 2 new arcs.
• The event is a curve or segment disappearing from P∩E:
Remove the event associated with this object. If it is a line segment, if either of its endpoints is within a bat in P∩E, the input is redundant.
| Next | |
|
|
|
| Applet |
|
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