可変形状ラベリング問題に対するアルゴリズム

スポンサーリンク

概要

論文の詳細を見る
障害物のある平面上の点集合に対するラベル付け問題で、LOFL(左整列可変ラベリング)という手法を提案する。各点に対して, 左整列静を持つ候補ラベル集合が与えられ, ラベルは候補から選ばれて共通のスケール比で拡大/縮小されて配置される。本論文では, 固定スケール比の入力に対して配置可能決定に対する最適なO((n+m)log(n+m))時間アルゴリズムと最大スケール比を求めるO((n+m)log^2(n+m))時間のアルゴリズムを与える。ここでnはラベル付けされる点の数であり、mは障害物の複雑度である。LOFLでは過去のラベリング手法と違い、様々な形のラベルを混用できる。そのため、図1にあるように、スケール比の大きなラベル付けを可能にする。
一般社団法人情報処理学会の論文
2000-05-19

著者

関連論文

もっと見る

スポンサーリンク