Crust and anti-crust

Abstract

We wish to extract the topology from scanned maps. In previous work [ 151 this was done by extracting a skeleton from the Voronoi diagram, but this required vertex labelling and was only useable for polygon maps. We wished to take the crust algorithm of Amenta, Bern and Eppstein [3] and modify it to extract the skeleton from unlabelled vertices. We find that by reducing the algorithm to a local test on the simple Voronoi diagram of point sites we may extract both the crust and the skeleton simultaneously. We show that this produces the same results as the original algorithm, and illustrate its utility with various cartographic applications.