The increased availability of interactive maps on the Internet and on personal mobile devices has created new challenges in computational cartography and, in particular, for label placement in maps. Operations like rotation, zoom, and translation dynamically change the map over time and make a consistent adaptation of the map labeling necessary. In this paper, we consider map labeling for the case that a map undergoes a sequence of operations over a specified time span. We unify and generalize several preceding models for dynamic map labeling into one versatile and flexible model. In contrast to previous research, we completely abstract from the particular operations (e.g., zoom, rotation, etc.) and express the labeling problem as a set of time intervals representing the labels' presences, activities, and conflicts. The model's strength is manifested in its simplicity and broad range of applications. In particular, it supports label selection both for map features with fixed position as well as for moving entities (e.g., for tracking vehicles in logistics or air traffic control). Through extensive experiments on OpenStreetMap data, we evaluate our model using algorithms of varying complexity as a case study for navigation systems. Our experiments show that even simple (and thus, fast) algorithms achieve near-optimal solutions in our model with respect to an intuitive objective function.
@cite_6 @cite_8 extended the ARO model to operations. They first showed that the ARO problem is NP-hard in that setting and introduced an efficient polynomial-time-approximation scheme (EPTAS) for unit-height rectangles @cite_6 . In a second step they experimentally evaluated heuristics, algorithms with approximation guarantees, and optimal approaches based on integer linear programming @cite_8 . A similar setting for rotating maps was considered by Yokosuka and Imai @cite_10 . Instead of ARO, they aimed at finding the maximum font size for which all labels can always be displayed without overlapping.
@cite_10 @cite_6 @cite_8
200670239 2182924349 2099151901 151632460
We consider the dynamic map labeling problem: given a set of rectangular labels on the map, the goal is to appropriately select visible ranges for all the labels such that no two consistent labels overlap at every scale and the sum of total visible ranges is maximized. We propose approximation algorithms for several variants of this problem. For the simple ARO problem, we provide a 3c logn-approximation algorithm for the unit-width rectangular labels if there is a c-approximation algorithm for unit-width label placement problem in the plane; and a randomized polynomial-time O(logn loglogn)-approximation algorithm for arbitrary rectangular labels. For the general ARO problem, we prove that it is NP-complete even for congruent square labels with equal selectable scale range. Moreover, we contribute 12-approximation algorithms for both arbitrary square labels and unit-width rectangular labels, and a 6-approximation algorithm for congruent square labels. We study a dynamic labeling problem for points on a line that is closely related to labeling of zoomable maps. Typically, labels have a constant size on screen, which means that, as the scale of the map decreases during zooming, the labels grow relatively to the set of points, and conicts may occur due to overlapping labels. Our algorithmic problem is a combined dynamic selection and placement problem in a sliding-label model: (i) select for each label ‘ a contiguous active range of map scales at which ‘ is displayed, and (ii) place each label at an appropriate position relative to its anchor point by sliding it along the point. The active range optimization (ARO) problem is to select active ranges and slider positions so that no two labels intersect at any scale and the sum of the lengths of active ranges is maximized. We present a dynamic programming algorithm to solve the discrete k-position ARO problem optimally and an FPTAS for the continuous sliding ARO problem. Map labeling encounters unique issues in the context of dynamic maps with continuous zooming and panning-an application with increasing practical importance. In consistent dynamic map labeling, distracting behavior such as popping and jumping is avoided. In the model for consistent dynamic labeling that we use, a label becomes a 3d-solid, with scale as the third dimension. Each solid can be truncated to a single scale interval, called its active range, corresponding to the scales at which the label will be selected. The active range optimization (ARO) problem is to select active ranges so that no two truncated solids overlap and the sum of the heights of the active ranges is maximized. The simple ARO problem is a variant in which the active ranges are restricted so that a label is never deselected when zooming in. We investigate both the general and simple variants, for 1d- as well as 2d-maps. The 1d-problem can be seen as a scheduling problem with geometric constraints, and is also closely related to geometric maximum independent set problems. Different label shapes define different ARO variants. We show that 2d-ARO and general 1d-ARO are NP-complete, even for quite simple shapes. We solve simple 1d-ARO optimally with dynamic programming, and present a toolbox of algorithms that yield constant-factor approximations for a number of 1d- and 2d-variants. We consider the following problem of labeling points in a dynamic map that allows rotation. We are given a set of feature points in the plane labeled by a set of mutually disjoint labels, where each label is an axis-aligned rectangle attached with one corner to its respective point. We require that each label remains horizontally aligned during the map rotation, and our goal is to find a set of mutually nonoverlapping visible labels for every rotation angle α ∈ [0, 2π) so that the number of visible labels over a full map rotation of 2π is maximized. We discuss and experimentally evaluate several labeling strategies that define additional consistency constraints on label visibility to reduce flickering effects during monotone map rotation. We introduce three heuristic algorithms and compare them experimentally to an existing approximation algorithm and exact solutions obtained from an integer linear program. Our results show that on the one hand, low flickering can be achieved at the expense of only a small reduction in the objective value, and on the other hand, the proposed heuristics achieve a high labeling quality significantly faster than the other methods.