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

Created from the Publication Database of the Vienna University of Technology.