Visualization of Spanners - The Applet
Instructions:
The applet can be used to visualize the
geographic neighborhood graph and the theta-graph. The following
functions are supported:
- a point can be added by clicking the left
mouse button.
- five random points can be added by clicking
the "+5"-button.
- a point can be deleted by clicking the
right mouse button.
- a point can be moved by dragging the left
mouse button.
- the number of cones can be set.
- show cones: by clicking on a point, the
cones around this point are shown.
- direction of edges: the definition of
the spanners define directed graphs in a natural way. This option
can be used to show the graphs as a directed or an undirected
graph.
After selecting two points P and Q, the
following options are offered.
- spanner path P -> Q: Shows the spanner
path from P to Q as constructed using the algorithm given in
Section 2.2. The graph
is considered as being directed.
- spanner path Q -> P: Shows the spanner
path from Q to P as constructed using the algorithm given in
Section 2.2.
The graph is considered as being directed.
- shortest path P -> Q: Shows the shortest
path from P to Q. The graph is considered as being directed.
- shortest path Q -> P: Shows the shortest
path from Q to P. The graph is considered as being directed.
- shortest undirected path: Shows the shortest
path between P and Q. The graph is considered as being undirected.
For each path, the applet gives the following
information.
- theoretical upper bound on stretch factor:
The value of t = 1 / (1 - 2 sin(theta / 2)),
where theta is equal to 2 pi divided by the number of cones.
- stretch factor graph: The actual stretch
factor of the graph.
- stretch factor path: The length of the
path divided by the Euclidean distance between P and Q.
- path with maximum sf: shows two points
whose stretch factor is maximum, together with the corresponding
path
After clicking on "enter demo'',
there are the following options.
- create graph:
By clicking on a point, it is shown how the edges starting at
this point are found.
- spanner path:
After selecting two points P and Q, the algorithm that constructs
a spanner between them is animated.
- both algorithms can be visualized in "step
mode'' (each click on the step button shows one step of the
algorithm) or in "run mode'' (one click starts the
entire algorithm).
Click to return to
Visualization of Spanners