[Back]

A. Gemsa, M. Nöllenburg, I. Rutter:
"Evaluation of Labeling Strategies for Rotating Maps";
ACM Journal of Experimental Algorithmics, 21 (2016), 1; 1 - 21.

We consider the following problem of labeling points in a dynamicmap 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 fullmap 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.

http://dx.doi.org/10.1145/2851493