Article,
Finding Optimal Sequences for Area Aggregation---A* vs.\ Integer Linear Programming
ACM Transactions on Spatial Algorithms and Systems, (2020)article 4 (40 pages).
DOI: 10.1145/3409290
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 A$^\star$
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
A$^\star$ finds optimal aggregation sequences for
more instances than the other two methods within a
given time frame.
