Polynomial Time Algorithms for Label Size Maximization on Rotating Maps

Map labeling is a problem of placing labels at corre-sponding 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 max-imization 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 la-bel 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.