Generalization of land cover maps by mixed integer programming

ABSTRACT

We present a novel method for the automatic generalization of land cover maps. A land cover map is composed of areas that collectively form a tessellation of the plane and each area is assigned to a land cover class such as lake, forest, or settlement. Our method aggregates areas into contiguous regions of equal class and of size greater than a user-defined threshold. To achieve this goal, some areas need to be enlarged at the expense of others. Given function that defines costs for the transformation between pairs of classes, our method guarantees to return a solution of minimal total cost. The method is based on a mixed integer program (MIP). To process maps with more than 50 areas, heuristics are introduced that lead to an alternative MIP formulation. The effects of the heuristics on the obtained solution and the computation time are discussed. The methods were tested using real data from the official German topographic data set (ATKIS) at scales 1:50.000 and 1:250.000.

REFERENCES

• 1: P. K. Bergey, C. T. Ragsdale, and M. Hoskote. A simulated annealing genetic algorithm for the electrical power districting problem. Annals of Operations Research, 121:33--55, 2003.
• 2: J. B. Cloonan. A note on the compactness of sales territories. Management Science, 19(4, Part 1):469--470, December 1972.
• 3: M. de Berg, M. van Kreveld, and S. Schirra. A new approach to subdivision simplification. In Twelfth International Symposium on Computer-Assisted Cartography, volume 4, pages 79--88, Charlotte, North Carolina, 1995.
• 4: E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.
• 5: M. R. Garey , D. S. Johnson , L. Stockmeyer, Some simplified NP-complete problems, Proceedings of the sixth annual ACM symposium on Theory of computing, p.47-63, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803884]
• 6: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 7: J.-H. Haunert and M. Sester. Propagating updates between linked data sets of different scale. In Proceedings of XXII International Cartographic Conference, 11--16 July 2005, A Coruña, Spain, 2005.
• 8: S. W. Hess and S. A. Samuels. Experiences with a sales districting model: Criteria and implementation. Management Science, 18(4, Part II):41--54, December 1971.
• 9: M. Schröder. Gebiete optimal aufteilen. PhD thesis, University of Karlsruhe, 2001.
• 10: Monika Sester , Karl-Heinrich Anders , Volker Walter, Linking Objects of Different Spatial Data Sets by Integration and Aggregation, Geoinformatica, v.2 n.4, p.335-358, December 1998 [doi>10.1023/A:1009705404707 ]
• 11: T. Shirabe. A model of contiguity for spatial unit allocation. Geographical Analysis, 37:2--16, 2005.
• 12: P. van Oosterom. The GAP-tree, an approach to 'on-the-fly' map generalization of an area partitioning. In J.-C. Müller, J.-P. Lagrange, and R. Weibel, editors, GIS and Generalization -- Methodology and Practice, number 1 in GISDATA. Taylor & Francis, London, 1995.
• 13: J. van Smaalen. Automated Aggregation of Geographic Objects. PhD thesis, Wageningen University, 2003.
• 14: A. A. Zoltners and P. Sinha. Sales territory alignment: A review and model. Management Science, 29(11):1237--1256, November 1983.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms

Keywords:
aggregation, generalization, mixed integer programming