[Back]

A. Gemsa, M. Nöllenburg, I. Rutter:
"Consistent Labeling Of Rotating Maps";
Journal of Computational Geometry, 7 (2016), 1; 308 - 331.

Dynamic maps that allow continuous map rotations, for example, on mobile devices, encounter new geometric labeling issues unseen in static maps before. We study the following dynamic map labeling problem: The input is an abstract map consisting of a set P of points in the plane with attached horizontally aligned rectangular labels. While the map with the point set P is rotated, all labels remain horizontally aligned. We are interested in a consistent labeling of P under rotation, i.e., an assignment of a single (possibly empty) active interval of angles for each label that determines its visibility under rotations such that visible labels neither intersect each other (soft conflicts) nor occlude points in P at any rotation angle (hard conflicts). Our goal is to find a consistent labeling that maximizes the number of visible labels integrated over all rotation angles.
We first introduce a general model for labeling rotating maps and derive basic geo- metric properties of consistent solutions. We show NP-hardness of the above optimization problem even for unit-square labels. We then present a constant-factor approximation for this problem based on line stabbing, and refine it further into an efficient polynomial-time approximation scheme (EPTAS).

http://dx.doi.org/10.20382/jocg.v7i1a15