Recently I managed to calculate the Minimum Spanning Tree (MST) of the Urban Tapestries dataset that was collected during the trial of 2004. From Wikipedia:

Given a connected, undirected graph, a spanning tree of that graph is a subgraph which is a tree and connects all the vertices together. A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree. A minimum spanning tree or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph has a minimum spanning forest.

Copyright notice: the present content was taken from the following URL, the copyrights are reserved by the respective author/s.

For the Urban Tapestries dataset, I had to adapt a version of Kruskal’s algorithm for minimum spanning trees that was greatly implemented by Prof. David Eppstein (thanks!). So the final result is visible below. Now the next step is to calculate a MST over the semantic distribution of the points and then find a way to compare these two trees to measure the distortion of the two layers.

Copyright notice: Google 2005, The GeoInformation Group 2006, the copyrights are reserved by the respective author/s.

Tags: anamorphosis maps, beta-skeletons, clustering, information metric, information visualization, map algorithms, maps, spatial clustering