An iterative displacement method for conflict resolution in map generalization

Cartographic generalization involves a trade-off between information content, accuracy and legibility. Conflict resolution, dealing with the problems of having too much information competing for too little space, is an important part of this process. For an iterative approach to conflict resolution two things are required: a measure of the acceptability of each intermediate map, and a strategy for finding a better one. Both the map quality measure and search strategy can have a large impact on the overall speed of the resulting process. This paper confines its map quality criterion to the minimum distance separating pairs of map features, an important component of legibility. This measure is combined with an iterative improvement technique. based on maximizing nearest neighbour distances, which attempts to find an acceptable solution where conflicts can be solved by displacement alone. The method also indicates those groups of features for which no such solution is possible. An experimental evaluation compares the method with one which uses simulated annealing and highlights its advantages with regard to generating many fewer candidate states and operating in a deterministic manner.