Label updating to avoid point-shaped obstacles in fixed model

Farshad Rostamabadi and Mohammad Ghodsi
Theoretical Computer Science
Volume 369, Issues 1-3, 15 December 2006, Pages 197-210
http://dx.doi.org/10.1016/j.tcs.2006.08.038

地図のラベル付け問題について．
平面上のいくつかの点に一定の大きさの正方形ラベルをついている．ここに新しい点が追加されたとき，ラベル付けを修正したい．ただし，ラベルは決められた2箇所の場所にしか置くことができず，そして，許される操作はラベルの置き換えとラベルの大きさ変更である．できるだけラベルの大きさを保ったままラベル修正を行なうにはどうしたらよいか？という問題を考えている．
この問題に対する効率よいアルゴリズムを与えている．

論文自体は読みにくい印象．問題設定自体の説明が分かりにくい．また，2SATを使っている先行研究のアプローチを「brute-force」といったり，追加される点がrandomに現れると言っているにも関わらず実際はarbitrarilyに現れることを意味していたり，と全体的にこなれてない印象を受ける．