A Fast Algorithm for Updating a Labeling to Avoid a Moving Point
Farshad Rostamabadi, Mohammad Ghodsi · Canadian Conference on Computational Geometry · 2004
Given a set of labeled points forming a valid map labeling, we are interested in a fast update of the labels if a point shaped object moves on an unknown path in the map. In this paper, there are labels that assumed to be axis-parallel, unit-length, and square-shaped, each attached to one point in the middle of one of its edges. We assume that a moving object can freely move on the map and sends notifications about its new positions. An updated labeling should include all labels with no overlaps, avoid the current position of the moving point, and use labels with length close to unit-size as possible. The existing algorithm for this problem runs in per each position notification. We present an algorithm that needs a preprocessing of time, but can update the map, for any new position of the moving point, in ! , where $#&%' is the minimum number of update operations needed. ( )+* , .-0/21 ' ,34*