Farshad Rostamabadi - Computer Engineering Department, Sharif University of Technology, Tehran, Iran
Mohammad Ghodsi - IPM School of Computer Science, Institute for Studies in Fundamental Sciences, Tehran, Iran

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.

Computational Geometry, Map Labeling, Online Labeling