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

无缩放地图：探索固定比例密集地图的模型和算法

• 批准号: 408056693
• 负责人: Professor Dr.-Ing. Jan-Henrik Haunert
• 金额: --
• 依托单位: Lehrstuhl für Geoinformation
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2018
• 资助国家: 德国
• 起止时间: 2017-12-31 至 2022-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/408056693?language=en
• 关键词: Zoomless; Maps; Models; Algorithms; Exploration

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.

交互式地图在导航系统和基于位置的服务中有着广泛的应用。然而，由于移动设备的显示尺寸有限，用户必须频繁地放大和缩小以检索详细信息和上下文信息。许多研究都集中在开发先进的缩放技术，以确保在地图中概括或放置标签时跨多个比例的某些一致性标准。因此，人们通常旨在避免缩放期间的突然变化。然而，由于大多数交互式地图严重依赖缩放，用户面临着地图范围和比例的频繁变化，这可能会分散注意力。因此，在这个项目中，我们的目标是简化从交互式地图中检索详细信息的过程，从而可以更频繁地解决典型的地图探索任务，而无需缩放到更大的比例。特别是，我们解决的任务是找到与一组涉及地理背景的用户指定标准相匹配的特定类别的对象（例如酒店或餐厅）。对于此类任务，我们考虑固定比例的地图，其中隐藏了一些信息，但可以通过交互访问。我们将此类地图称为无缩放地图。无缩放地图的一个基本示例是由多个页面组成的地图，每个页面在固定背景地图前面显示一组不同的对象。通过从一个页面导航到另一个页面，用户可以检索所有对象而无需缩放。这种基本类型的无缩放地图已经带来了未解决的算法问题。具体地，每个要显示的对象必须被分配给一个页面，使得每个页面具有高制图质量，重要的对象出现在较早的页面上，并且页面的总数较少。基于无缩放地图的基本模型，我们将增加更多的灵活性，例如，通过对对象进行聚类并显示每个聚类而不是其每个元素，并允许用户扩展地图中显示的任何聚类。该项目旨在针对要求和质量标准对无缩放地图进行形式化的模型，以及根据这些模型计算高质量无缩放地图的算法。我们的目标是足够通用的算法框架来应对不同的模型变体，而不是针对受限情况的专门算法。一方面，我们将开发基于数学编程的高效精确算法和精确方法，以生成相对于底层模型最优的地图。另一方面，我们还致力于高效的启发式算法，实时计算足够质量的地图。我们将与用户一起评估精确方法返回的最佳解决方案，以确定我们的模型是否充分反映了制图质量。此外，我们会将启发式结果与最佳解决方案进行比较，以评估我们在质量方面损失了多少。