重み付きL_∞距離Voronoi図の構成と文字配置問題
スポンサーリンク
概要
- 論文の詳細を見る
平面上にn個の点が与えられたときこれらの点の勢力圏をあらわすVoronoi図は、計算幾何学の数多くの基本的な問題を解くのに用いられる有益な手法である。各点の勢力圏を定義するときの距離は一般にはEuclid距離を用いるが、その他にもL_1距離やL_∞距離を用いた方が効率よく解ける問題もある。本稿では、平面上の各点にそれぞれ異なる正の値の重みを持たせてL_∞距離で定義したVoronoi図を構成するアルゴリズムを概説する。これはDavenport-Schinzel列を用いるとO(n^2log n)時間で構成できる。さらに、この図が文字配置問題において地図が動的に変化する場合の簡単なバージョンに適用できることを述べる。重み付きVoronoi図については、Euclid距離を用いて構成すると、最悪の場合にO(n^2)のVoronoi辺、Voronoi点が存在することが示されており、その計算複雑度がO(n^2)であることが分かっている。またDavenport-Schinzel列は、関数集合の最小値すなわち下側エンベロープを求めるときに用いられる手法で、例えばn個の関数が2変数関数でそれらが部分的に線形である場合、O(n^2α(n)log n)の手間で下側エンベロープを求めるアルゴリズムが文献で紹介されている。本稿では、これらの特別な場合としてL_∞距離によるVoronoi図および1変数関数のDavenport-Schinzel列を用いてアルゴリズムの計算複雑度の改良を図る。
- 一般社団法人情報処理学会の論文
- 1989-10-16
著者
関連論文
- 利用者インターフェースとしての文字自動配置機能(計算アルゴリズムと計算量の基礎理論)
- 3次元の点集合のL_1平面近似問題に対する線形時間アルゴリズム
- 既存のCADシステムに対する設計データベース機能の追加について
- 文字の可読性を考慮した対話的地図表示機能
- 計算幾何学と折れ線近似問題
- 3次元空間に与えられた2次元集合間のマッチングについて
- 拡大縮小を考慮した点集合の正方格子度を求めるアルゴリズム
- 凸多角形の多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図(アルゴリズムと計算量の理論)
- 平行移動する複数の点集合または線分集合に対するVoronoi図の複数さと文字配置への応用
- 重み付きL_∞距離Voronoi図の構成と文字配置問題
- 連結性を考慮した近似折れ線による曲線の階層管理
- 内点法の平面ネットワークフロー問題への適用(アルゴリズムと計算量の理論)
- 線形計画法の新解法について
- 線形計画法と計算の複雑さ
- 線形計画問題に対する乗法的罰金関数法について(線形計画法の最近の発展)