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.