PCG
PCG copied to clipboard
Add Distance Wagner method
Ward mentioned that we should add a new build method which uses the distance Wagner. This is described in detail on p. 165 of the Systematics text book. Roughly it works as follows: given an already constructed tree:
[...] [...]
│ e_ij │
v_i ────────── v_j
│ │
[...] [...]
If we wish to add vertex v_k
to this tree then we compute the distance:
d(v_k, e_ij) = 1/2 (d(v_k, v_i) + d(v_k,v_j) - d(v_i,v_j)
If v_i
and v_j
are already internal nodes in the tree then these distances are computed in terms of computations involving only the distances between the leaves in the subtrees to which they are attached. One then adds a new internal vertex and attaches v_k
to the edge with the minimal distance. One nice thing about this method is that we do not need to compute any medians or perform any traversals as it is based entirely on the distance matrix between the leaves. This means we do not need to construct intermediate trees but instead can use a smaller data structure for tracking the distance information.
Note: I think it is the case that if the metric is an ultrametric then this is exactly the distance but otherwise is an overestimate because of the triangle inequality. The textbook indicates that this method might cause problems for non-metric distances.
Ward noted that having this kind of distance information might also be useful when performing refinements as this can provide candidate edges along which to perform SPR-type moves.