next up previous contents
Next: Interpretationevaluation, and use Up: Choosing good maps Previous: Note 2: High dimensionality.

Note 3: Computational complexity.

The proposed measure is fairly computationally intensive. It requires searching for the shortest path between each pair of units on the map, based on the distances between the reference vectors in the data space. The measure can, however, be computed using dynamic programming (cf., e.g., Sedgewick, 1988), which reduces the complexity. A coarse estimate of the measure, suitable for very large maps, might also be obtained by computing the distance along the reference vectors of the units that lie on the shortest path along the map lattice, or even by computing the distance along the map lattice.

Sami Kaski
Mon Mar 31 23:43:35 EET DST 1997