On exactitude in geographic information science

There are a wide variety of clustering and optimization algorithms which work in vector spaces, but relatively fewer that work on graphs. An algorithm to embed road network metrics into vector spaces is presented in this document, which makes a number of existing algorithms available for GIS applications. The approach taken is to modify and extend the Graham-Winkler graph factoring algorithm to enable the construction of l 1 embeddings. While similar algorithms have been known in much more limited contexts, this work provides the first analysis and experimental results to show that this approach is applicable to road networks. A number of applications are also discussed.