Euclid距離による凸多角形の多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図

概要

論文の詳細を見る
多角形配置問題とは,与えられた多角形Pを他の多角形Qの内部に配置するという問題である.この問題は,モーションプラニングとも密接に関係があり,いろいろな面から研究がなされている.本稿では,何種類かのEuclid距離をもちいた多角形max-imin配置問題を考える.最も基本的なmaximin配置問題は,Pの任意の点とQの任意の点のEuclid距離の最小値が最大となるように凸多角形Pを多角形Qの内部に配置するという問題である.さらに,Pをいくつか一直線上に並ぶようにして,同様のmaximin配置問題を解くことも考える.直感的にいえば,多角形PまたはそのいくつかのコピーをQの境界からなるべく離れるようにQの内部に置く問題を考えることであると言ってよい.似たような問題に,Pに相似な最大の多角形をQの内部に配置するという問題があり,これについてはFortune[F]やChewとKedem[CK]で考察されている.しかし,彼らは凸距離関数を用いており,Euclid距離を用いた問題については,これまでに研究がなされていない.ここでは,新しいVoronoi図(P-Euclid Voronoi図と呼ぶ)を定義することによってこれらのmaximin配置問題に対する効率の良いアルゴリズムを紹介し,それらの組合せ的複雑度についての解析を行なう.計算複雑度の解析においては,Davenport-Schinzel列の理論を用いる.凸多角形の多角形内への配置問題は,地図の中へ地名などを記入するときにも現われる.このような場面では,文字列は長方形で表わされ,領域は多角形で表現される.長方形を,上記の意味でのmaximin問題の解となるように多角形の内部に置きたい.また,文字列を1つの長方形として捕らえるのではなく,すでに置かれている文字と重ならないように,かつ,一定の間隔で一列に並ぶように各文字を置くことを考える。このような問題を解くためには,穴のある多角形の内部に正方形のコピーを一定の間隔で配置する問題を考える必要がある。本稿で扱うmaximin配置問題と得られた結果,また,それに関連してすでに得られている結果をまとめると次のようになる.Pはm個の辺を持つ凸多角形,Qはn個の辺を持つ多角形(または多角形領域)とする.[figure] (P1)平行移動だけを用いてPの任意の点とQの任意の点とのEuclid距離の最小値が最大となるように凸多角形Pを多角形領域Qの内部に置く.問題(P1)は,平行移動によりPの相似な図形のうち最大のものをQの内部に配置する問題と関係が深い.Pの相似な図形で最大のものを配置する問題についてはPに関する凸距離関数に対するQのVoronioi図を用いてO(mnlogmn)の手間で解ける([F]).(P1)もO(mmlogmn)の手間で解ける([AIIT]}).(P2)回転と平行移動によってPの任意の点とQの任意の点とのEuclid距離の最小値が最大になるように凸多角形Pを多角形領域Q内に配置せよ.(P2)はO(m^4λ_<16>(mn)logmn)の手間で解くことができる.ここで,λ_<16>(mn)は位数16のDavenport-Schinzel列の最大長を表わす.一般に,λ_δ(N)はNにほとんど線形な関数であることがわかっている.(P3)Q内にPのk個のコピーを次のように配置する.Pのコピーは水平線上に並び,コピー間の距離hと、Pの任意の点とQの任意の点の間の距離の最小値が最大となるようにする.ここで,hは与えられた定数h_0>0以上であるような変数である.k=2とk≥3の場合にそれぞれ問題(P3)は,O(m^2n^2logmn),O(k^6m^3n^3logkmn)の手間で解ける.
一般社団法人情報処理学会の論文
1990-09-04

Euclid距離による凸多角形の多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図

スポンサーリンク

概要

著者

関連論文

スポンサーリンク