Article ID: | iaor20121030 |
Volume: | 30 |
Issue: | 2 |
Start Page Number: | 144 |
End Page Number: | 163 |
Publication Date: | Jun 2001 |
Journal: | Algorithmica |
Authors: | Gold C, Snoeyink J |
Keywords: | graphical methods, maps, topology |
We wish to extract the topology from scanned maps. In previous work [GNY] 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 et al. [ABE] and modify it to extract the skeleton from unlabelled vertices. We find that by reducing the algorithm to a local test on the original Voronoi diagram we may extract both a crust and a skeleton simultaneously, using a variant of the Quad‐Edge structure of [GS]. We show that this crust has the properties of the original, and that the resulting skeleton has many practical uses. We illustrate the usefulness of the combined diagram with various applications.