Incremental Labeling in Closed-2PM Model

We consider an incremental optimal label placement in a closed-2PM model where labels are disjoint axis-parallel square-shaped of maximum length each attached to its cor- responding point on one of its horizontal edges. Our goal is to e±ciently generate a new optimal labeling for all points after each point insertion. Inserting each point may require several labels to °ip or all labels to shrink. We present an algorithm that generates each new optimal labeling in O(lg n + k) time where k is the number of required label °ips, if there is no need to shrink the label lengths, or in O(n) time when we have to shrink labels. The algorithm uses O(n) space in both cases.

Keywords:

Computational Geometry , Map Labeling , Online Labeling