Zoomless Maps: Models and Algorithms for the Exploration of Dense Maps with a Fixed Scale

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

Interactive maps have found a huge range of applications in navigation systems and location-based services. Due to the limited display sizes of mobile devices, however, users have to zoom in and out frequently to retrieve both detailed information and information on context. A lot of research has focused on developing advanced techniques for zooming that ensure certain criteria of consistency across multiple scales when generalizing or placing labels in a map. Thereby, one usually aims to avoid abrupt changes during zooming. Nevertheless, since most interactive maps heavily rely on zooming, users are faced with frequent changes of the map extent and scale, which can be distracting. Therefore, in this project, we aim to ease the retrieval of detailed information from an interactive map in such a way that typical map-exploration tasks can be solved more frequently without zooming to a larger scale. In particular, we address the task of finding an object of a certain category (for example, a hotel orrestaurant) that matches a set of user-specified criteria involving geographic context. For such tasks, we consider maps of a fixed scale in which some information is hidden but accessible via interactions. We refer to such maps as zoomless maps. A basic example of a zoomless map is a map that consists of multiple pages, each of which displays a different set of objects in front of a fixed background map. By navigating from page to page a user can retrieve all objects without zooming. This basic type of zoomless map already poses unsolved algorithmic problems. In particular, each object that is to be displayed has to be assigned to a page such that each page is of high cartographic quality, important objects appear on early pages, and the total number of pages is small. Based on this basic model of a zoomless map we will add more flexibility, for example, by clustering objects and displaying each cluster instead of each of its elements and allowing a user to expand any of the clusters displayed in the map.This project aims at models for the formalization of zoomless maps with respect to requirements and quality criteria as well as at algorithms for computing zoomless maps of high quality according to those models. We aim at algorithmic frameworks that are general enough to cope with different model variants rather than at specialized algorithms for restricted cases. On the one hand, we will develop efficient exact algorithms and exact methods based on mathematical programming to generate maps that are optimal with respect to the underlying model. On the other hand, we also aim for efficient heuristics for computing maps of sufficient quality in real time. We will evaluate optimal solutions returned by an exact method with users in order to find out whether our models adequately reflect cartographic quality. Moreover, we will compare the results of our heuristics with optimal solutions to assess how much in terms of quality we lose with them.