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 geometric 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 pro ... mehrblem based on line stabbing, and refine it further into an efficient polynomial-time approximation scheme (EPTAS).