سال انتشار: ۱۳۸۴

محل انتشار: یازدهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۵

نویسنده(ها):

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.