Simultaneous Simplification and Aggregation for Interactive Maps

点击翻译按钮获取中文摘要

To use a geographic data set in a spatial analysis or for a map, one often needs to coarsen its granularity. In geographic information science and cartography, this task is termed generalization. Project C1 will contribute to automated generalization by developing algorithms for detecting groups of objects in a geographic data set and computing a single representative and simplified object for each group. As two concrete use cases we will study (i) the delineation of regions of human activity based on geo-tagged social-media data and (ii) the derivation of polygons corresponding to built-up areas, settlements, and larger urban agglomerations from footprints of individual buildings. In both cases we aim at interactive maps that allow their users to zoom through different scales and to change the map's point of reference in time or its interval of reference in time. For example, by dragging a time slider, a user can change the map's point of reference in time to obtain an animation of urban growth over multiple years. We will develop an approach that treats the detection of groups of objects, the aggregation of each group to a polygon, and the simplification of polygons as a single task. Our central hypothesis is that such an integrated approach yields substantially better solutions than the currently dominating approach of first aggregating and then simplifying. The development will follow an algorithm engineering process including the modelling of problems, the design of efficient algorithms, mathematical analyses, and experiments.