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
2748600169 151632460
Map labeling is a problem of placing labels at corresponding graphical features on a map. There are two optimization problems: the label number maximization problem and the label size maximization problem. In general, both problems are NP-hard for static maps. Recently, the widespread use of several applications, such as personal mapping systems, has increased the importance of dynamic maps and the label number maximization problem for dynamic cases has been studied. In this paper, we consider the label size maximization problem for points on rotating maps. Our model is as follows. For each label, a point is chosen inside the label or on its boundary as an anchor point. Each label is placed such that the anchor point coincides with the corresponding point on the map. Furthermore, while the map fully rotates from 0 to 2π, the labels are placed horizontally according to the angle of the map. Our problem consists of finding the maximum scale factor for the labels such that the labels do not intersect, and deciding the place of the anchor points. We propose an O(n log n)-time and O(n)-space algorithm for the case where each anchor point is inside the label. Moreover, if the labels are of unit-height (or unit-width) and the anchor points are on the boundary, we also present an O(n log n)-time and O(n)-space algorithm. 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.