n点の集合P, P の2点間の距離d :P ×P →R, 整数kが与えられたとき, 指定され たコストを最大化するようなk個の点集合S ⊂ P を求める問題をdispersion問題とい う. 指定するコストにより様々な問題が知られている[15, 16, 20, 23].
P が平面上の点集合とみなせるときdispersion問題はNP困難である[20, 23]. P が直 線上の点集合とみなせるとき, dipsersion問題を解く動的計画法によるO(nlogn+kn) 時間アルゴリズム[20]が知られている. また, パス分割問題へ帰着してこれを行列探索 法[13]で解くことにより, O(n)時間で解くこともできる. これを拡張して, P が円周上 の点集合とみなせるときもO(n)時間で解くことができる[22]. しかし, P が円周上の点 集合とみなせるときのdispersion問題を解くO(n)時間アルゴリズム[22] はとても複雑 であり,実装が難しい.
本節では, P が円周上の点集合とみなせるときの,k = 3のときのdispersion問題を解 く単純なO(n)時間アルゴリズムを与える.
S中の最も近い2点間の距離minp,q∈S{d(p, q)}を集合S ⊂P のコストcost(S)とする.
このminp,q∈S{d(p, q)}が最大のS ⊂ P を求める問題をdispersion問題(k-dispersion問 題)という.
5.1 円周上の 3-dispersion 問題を解くアルゴリズム
本節ではP ={p1, p2, . . . , pn}が円周上の点集合とみなせるときの3-dispersion問題を 解くO(n)時間アルゴリズムを与える. ここで,p1, p2, . . .は円周上に時計回りに現れると する.
S ⊂P (|S|= 3)中の最も近い2点間の(円弧の)距離minp,q∈S{d(p, q)} をSのコスト cost(S)とする.
いくつかの定義を行う. pi ∈P が与えられたとき, 点pℓi, pri をpi, pℓi, pri が円周上の正 三角形の角であるような点と定義する.
中心角が120◦のpiとpℓi 間の円弧をAℓ = (pi, pℓi)とし, 中心角が120◦のpℓi とpri 間の (開)円弧をAt = (pℓi, pri), 中心角が120◦のpri とpi間の円弧をAr = (pri, pi)とする. (図
5.1参照.)
図 5.1: Aℓ, At, Arの図.
piを基準に, pℓ ∈Aℓかつpr ∈Arである集合S ={pi, pℓ, pr}をType-LRと定義する.
同様に, piを基準に, pℓ ∈ Aℓかつpr ∈ AℓであるSをType-LLと定義し, piを基準に, pℓ ∈Arかつpr ∈ArであるSをType-RR,piを基準に,pℓ ∈Aℓかつpr ∈AtであるSを Type-LT, piを基準に, pℓ ∈ Atかつpr ∈ ArであるSをType-TR, piを基準に, pℓ ∈ At かつpr ∈AtであるSをType-TTと定義する.
次の補題が成り立つ.
補題.5.1. P が円周上の点集合とみなせるとき, 3-dispersion問題の最適解Sはある点 pi ∈Sを基準にしたType-LRまたはType-TTである.
証明. S ={pi, pℓ, pr}とし,piを基準としてpℓとprは円周上に時計回りで現れるとする.
もしSがpiを基準としたType-LLならば, Sはpℓを基準としたType-LRである. (図 5.2参照.) もしSがpiを基準としたType-RRならば,Sはprを基準としたType-LRで ある. (図5.2と同様.) もしSがpiを基準としたType-LTならば, (1) pℓとpr間の円弧 の中心角が120◦未満であり, Sはpℓを基準としたType-LRである, (図5.3参照.) また は(2) pℓとpr間の円弧の中心角が120◦以上であり, Sはprを基準としたType-TTであ る. (図5.4参照.) もしSがpiを基準としたType-TRならば, (1) pℓとpr間の円弧の中 心角が120◦未満であり, Sはprを基準としたType-LRである, (図5.3と同様.) または (2) pℓとpr間の円弧の中心角が120◦以上であり, Sはpℓを基準としたType-TTである.
(図5.3と同様.) 2
図 5.2: piを基準としたSがType-LLの例.
図 5.3: piを基準としたSが
Type-LTで(1) pℓとpr間の 円弧の中心角が120◦未満の例.
図 5.4: piを基準としたSが
Type-LTで(2) pℓとpr間の 円弧の中心角が120◦以上の例.
補題5.2. (a) もし解S ={pi, pℓ, pr}がpiを基準としたType-TTならば,時計回りにpℓi の次のP の点がpℓであり, 反時計回りにpri の次のP の点がprである.
(b) もし解S = {pi, pℓ, pr}がpiを基準としたType-LRならば, 反時計回りにpℓi の次 のP の点がpℓであり,時計回りにpri の次のP の点がprである.
証明. (a) SはType-TTなので, min{d(pi, pℓ), d(pℓ, pr), d(pr, pi)} = d(pℓ, pr)である.
よって,d(pℓ, pr)が最大となるようにSを選択すると, Sは最大コストとなる.
(b) SはType-LRなので,min{d(pi, pℓ), d(pℓ, pr), d(pr, pi)} ̸=d(pℓ, pr)である. よって, d(pi, pℓ)とd(pi, pr)が最大となるようにSを選択すると, Sは最大コストとなる. 2 各pi ∈ P について, 時計回りにpℓi の次のP の点を計算する. この計算にかかる時間 はO(n)である. 同様に,各pi ∈P について, 反時計回りにpri の次のP の点を計算する.
この計算にかかる時間はO(n)である. これらを前処理として実行する.
前処理より, 各pi ∈P について, O(1)時間で(1) コストcost(S)が最大であるpiを基 準としたType-LRのS, (2) コストcost(S)が最大であるpiを基準としたType-TTのS を計算し, コストが大きい方を選択できる.
したがって,次の定理が成り立つ.
定理5.3. P を円周上の点集合とみなせるとき, 3-dispersion問題を解くO(n)時間アル ゴリズムがある.