Why pictures might look wrong (but aren't really).
Because the PWIT is an infinite graph, the
notions of MST and TSP
are different from what you're used to.
The MST is really a forest with infinite tree-components;
the TSP is actually a collection of doubly-infinite paths.
Very short edges, where the end-vertex discs overlap, are not shown.
The default ``radius-limited" picture shows only edges
for which both end-vertices are within the window
(centered on the current root).
Thus you will often see vertices which have fewer than the
correct number of edges (1 for MM, 2 for TSP) visible.
To make these edges visible, first re-root at vertex of interest.
Then ``zoom out". If the edges still don't appear, switch
to the alternate ``depth-limited" picture. This will show
that the missing edge is an unusually long edge.
The program simulates only a finite region of the PWIT.
By continually re-rooting you will reach the boundary of
this region, and edges going across the boundary are not simulated.
You can tell whether you have reached the boundary by switching to
``depth-limited" picture; if the root has only one edge
then it is on the boundary.
Use ``step toward root" or ``reset".
You might think that very short edges should be in the optimal
solutions with very high probability. For MST this is true;
every edge of length less than 1 is in the MST.
In the other cases it is wrong; the limit probability
(as edge-length tends to 0)
equals 0.5 for MM and is about 0.76 for TSP.
- The intrinsic random variability of the PWIT is more than you
might think. Consider for instance the number of vertices (including
the root) within the default window (radius 3). This has
Geometric distribution with mean e^3 = 20.1, which implies
- with chance 1/10 we see only 1 or 2 vertices in the window
- with chance 1/10 we see 46 or more vertices in the window.
- More subtle things only an expert