Finding Optimal Sequences for Area Aggregation-A* vs. Integer Linear Programming

Dongliang Peng*, Alexander Wolff, Jan Henrik Haunert

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
27 Downloads (Pure)

Abstract

To provide users with maps of different scales and to allow them to zoom in and out without losing context, automatic methods for map generalization are needed. We approach this problem for land-cover maps. Given two land-cover maps at two different scales, we want to find a sequence of small incremental changes that gradually transforms one map into the other. We assume that the two input maps consist of polygons, each of which belongs to a given land-cover type. Every polygon on the smaller-scale map is the union of a set of adjacent polygons on the larger-scale map. In each step of the computed sequence, the smallest area is merged with one of its neighbors. We do not select that neighbor according to a prescribed rule but compute the whole sequence of pairwise merges at once, based on global optimization. We have proved that this problem is NP-hard. We formalize this optimization problem as that of finding a shortest path in a (very large) graph. We present the Ag algorithm and integer linear programming to solve this optimization problem. To avoid long computing times, we allow the two methods to return non-optimal results. In addition, we present a greedy algorithm as a benchmark. We tested the three methods with a dataset of the official German topographic database ATKIS. Our main result is that Ag finds optimal aggregation sequences for more instancesthan the other two methods within a given time frame.

Original languageEnglish
Article number4
Number of pages40
JournalACM Transactions on Spatial Algorithms and Systems
Volume7
Issue number1
DOIs
Publication statusPublished - 2021

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care

Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

  • compactness
  • Continuous map generalization
  • land-cover area
  • shortest path
  • type change

Fingerprint

Dive into the research topics of 'Finding Optimal Sequences for Area Aggregation-A* vs. Integer Linear Programming'. Together they form a unique fingerprint.

Cite this