計算幾何学と並列アルゴリズム
今井浩ヘ今井桂子林
111
l
川
11川
11川
11川
11川
11川
11川川
11川川|川川
11 川川|川川
11 川川
11l川|川
川
11川
11山
11川
11川
11川
11川川
11川川
11川川
11川川|川川|川川
11 川川
11川
11川
11川
11川
11川
11川
11川
11川
11川川
11川
11川
11川川
11川|川川11 川川
11l川川|川川|川川
川川
11川
11川
11川
11川
11川
11川川
11川川|川川
11 川川|川川|川川|川川|川川
11 川川
11川
11川
11川
11111川
川
11川
11川
11111
川111
川川
l川川川|川川|川川
11川 川
11川
11川
11川
11川
11川
11111川
川
11川
11川川
11川川
11川川|川川|川川|川川|川川|川川
11 川
11川
11川川
11川
11川
11川
11川
11川
11川
11川川
11川
11111
川川
川
11川川
11川川
11川川|川川
11 川川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11111
川
川川
11川川|川川|川川
11 川川|川川
11 川
11川
11川
11川
11川
11川
11川
11川
11111
川1111
川
川川
11川
11川川|川川|川川|川川|川川|川川|川川|川11川
11l日1111川川
川
11川川|川川
11 川川|川川|川川
11 川川
11川
11川
11川
11川
11111
川
川
11川
11川川
11川川
11川川
11川川|川川|川川
11 川
11川
11川
11川
1111111川川川
11川川
11川川|川川|川
11 川川
11川
11川
1111111川
川川|川川|川川
11 川川
11川
11111
川
川
11川
111111川川
川川|川川|川川
11 川川
11川

1.

法について説明しよう.具体的な例題で説明した方がよ

はじめに計算幾何学では，その応用の広がりとともに，解くべいが，この手法の面白さの 1 つは，その考えの漠然としき比較的新しい問題がまだまだ多く，そのような問題にたところから生まれる汎用性でもあるので，一般的な枠対する研究では，逐次アルゴリズムに関する研究が中心組だけはまず大きな枠組で説明しておく.

であるといえる.そういう中で，計算幾何の並列アルゴ

Megiddo のこの手法は，次のようなものである.

リズムに関する包括的な研究もいくつかあるが，一般的列計算環境としては，理想的なものを考える.すなわちには計算幾何学での並列アルコリズム研究というのは，成熟するにまだ至っていないような状況である.

P 台プロセツサがあれば，アルゴリズムさえ並列化可能ならば，速度が P 倍速くなるというものである.

ある問題 A を解く次のような性能の逐次アルゴリズム

しかし，一方で並列アルゴリズムの一般の手法を計算幾何の幅広い問題に適用して，効率的な逐次アルゴリズムを構成するということが，最近注目を浴びている.この手法は，中核となるアイデアの提案者である Megi­

ddo[5]の名で、呼ばれたり，と並列アルゴリズムがあったとする:(1)

Cole [3]によっ

この手法は， Megiddo の提案の後，問題 A は逐次的に解けば九時間の手間で解け，(訪問題 A は P プロセツザで T p 時間の手間で解ける.

一般に ， (2) のような並列アルゴリズムをプロセ γあるいはパラメリトックサーチ (parametric search) と呼ばれたりしている.

サしかない逐次計算機の上で O(PT p ) 時聞かけて実行すること(シミュレートすること)は容易である.に，てさらに拡張されている.
本稿では，このような並列アルゴリズムと逐次アルゴリズムの絡みで生まれてきた手法の説明をし，それによって効率よく解ける計算幾何の問題のいくつかについて触れていく.これは，並列計算機でより高速に問題を解ゴリズムであるが，その設計過程で並列的な発想を必要(逆九時間の逐次アルゴリズムを自動的に変換して，P プロセッサの並列計算機で O(Ts/P) 時間で問題を解くことは，一般には非常に難しく，このことこそが，単に逐次アルゴリズムを研究するだけでなく，並列アルゴリズムを研究する必要性を示している)

この問題 A を繰り返し解くことにより解ける問題 B をくという話ではなく，今の逐次計算機上で問題を高速に解くとし、う話である.最終的に得られるものは逐次アル並考える.問題 B がその中で問題 A を解く回数を C とするとA を解くのに逐次アルゴリズムを用いると，問題 Bとするものである.そういった意味で，これを計算幾何は O(CTs ) の手間で解けることになる.

での並列アルゴリズムの話として述べるのはおかしいか

くための逐次アルゴリズムの代わりに並列なアルゴリズ

一方A を解もしれないが，逆に見れば，出てくるものが効ヰ量的な逐ムの方(逐次的に実行して)を用いることによって，問次アルゴリズムということですぐに役立つものであるの

題 B を逐次的に O(CTpP) 時間で解くことは自明であで，ここて、は並列性を内部にもった逐次アルゴリズムとる.しかし，じつは (P があまり大きすぎないなどといっしてとりあげていく.

た条件が成り立っているときには)逐次的に O(TpP+

この手法によって従来の方法より効率的に解ける計算

幾何問題の中には，多くの施設配置問題も含まれており，この手法自体，数理計画と密接な関係をもっているとを Megiddo は示した.
Megiddo のこのパラメトリックサーチ手法は，問題A として整列(ソーティング)とそれに関した問題をよと L 、う意味でも興味深し、と思われる.

2. パラメトリックサーチ
まず，CTplogP) 時間で問題 B を解くことができるというこ

Megiddo の与えたパラメトリックサーチの手く用いる.ただし，問題 A はこれらの問題のみに限られるのでなく，一般に効率のよい並列アルゴリズムが存在する問題であればなんでもよい.ここでは，例として，

* いまい

ひろし

料いまいけいこ386 (32)東京大学理学部情報科学科

ある最適化問題 B で，整列問題 A を部分問題とするよう

中央大学理工学部情報工学科なものを考える.

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

今，整列問題 A に対して速い並列アルゴリズムが得られているとする(実際，存在する).

何事)とん (x引を比較することができることを説明しまた，問題 B に対よう.もし，直線 I， (x) と 12(X) が並行であればすべしては A を解くことによって，あとは高速の逐次アルゴての z に対して I， (x)> 12(X) , fì(x) =f2 (x) , fì(x) </2

リズムを得られるとし，次のような仮定 1 ， 2 をおく.

(x) のどれかが成り立つ

x=x本でもそうである .fì

(仮定 1 ) 問題 B は，整列を行なったのちは，簡単に解(x) と 12(X) が並行でないとし，くことができるが，整列の過程での 2 つの要素の比較はなく一般性を失なうこと

a ， >a2 と仮定してかまわない.

このときは I， (x)ある問題を解くことに対応して高価であり，それには定=/2(X)数時間より長い C( n) の手聞がかかる.普通 ，

x>xo に対しては fì(x)> f2 (x) であるし ，C( n) はとなる x=xo が一意的に存在する.

そして，x<xo に対O(n) とか O(n logn) である.口しては I， (x) </2(X) となることがわかる.ここで，も(仮定 2) (一括処理条件 )m 個の比較 C h … ， C怖を考えし .x *>xo であれば ，fì(x*)>J主 (x*) ，x*=xo であれ

た時，これらの比較の集合に次のような意味での順序

ば ， 1 , (x*)=/2(X*) , X本 <xo であれば， f (x*)</2(X事)C.ω 孟・三五 Cπ〈耐をつけることができる(ここでの比較となる.このように比較に答えることは ， x*<xo , x市=

C とは答が“ yes" か“ no" であるような聞い“ c ， <C2?"

xo,としている).ここでつけた順序によれば，もし C.( ρ にされる.このためには ， I(x o ) を (O(n) の手間で)評

対する答が“ yes" なら，CIfC1 h …, C.(j_ll の答は“ yes"価し ， /(x) は増加関数であることから ， I(xo)<0 ならであり ， C.<jl に対する答が“ no" なら ， C.(j+山…， C.<mlx*>xo であるし ， I(xo)=o なら x*=xo， l(xo)>O なx*>x o のどれが成り立っかを決定することに帰着の答は“ no" でなければならない.この条件が成り立っ

ら x*<xo であることがわかる.したがって O(n) 時間ていると，たとえば C.(m/2l の答をひとつ計算するだけ(=O( C( n)) 時間)で比較が行なえる.これで，一般的で，少なくとも他の半分の答を決定することができ，こな枠組での仮定 1 が満たされていることがわかった.

れをうまく行なっていくことにより2 つの比較の相対的な 11頂序の決定はかなり速く行なえるようにできる.口

次に，仮定 2 の一括処理条件が満たされていることを見ょう.

一括処理条件を示すためには，比較が順序づけられることを示さなければならない.

“λ ， (x事) <li2からは手法が具体的にどのように進むかを例で見ていこ(x*)?" という m 個の比較 C t を考える.

ここで ai'>う

ai2, 1 :O;; i 孟 m とする.各比較は ， x*>xi' x本 =Xi) x*

ここまで‘は，一般的な枠組で話を進めてきたが，ここn 個の線形増加関数 It(x)=aix+bi ，ai>O ， I:ζZ:O;; n を考える.中央値関数を I(x)=median [f， (x) ，・・，

<引を決めるための値引を決定する.

In(x)J と定義する .

順番に並べることができる:らω 三三… :O;; X.< 耐・比較 C t意する.

I(x) も増加関数であることに注

ここで ， /(x勺 =0 となる x* を求めることを問題とする(問題 B).

もし ，x* を求めずに li(X*)=1(xホ)となる z を見つけることができれば ，ことになる(あと ，x* を求めたli(X)=O となるような z を求めればよし、かられ

これらの値をにも同じ順序をつける : C. C1J:O;;・・ 2王 C.(ml・ここで x*>

Xtr<j> なら i :O;; j に対して x* くらcρ ， x*<x.(jl なら i~J に対して x*>x.ωとなることに注意すると ，C.
<jlの答が得られれば， C1!'(1 h …, C.(j-'h または C.(j +1 h …，C.( 耐の答が得られたことになる.すなわち，この答えではどうやって x* を求めずに It( エホ )=/(x*)

る i を求めることができるのだろうか.とな

この li(X*)=

median[f, (x本)，…，ん (xホ )J となる i を知るためには x*がわかった側については，具体的に各比較を評価することなくすんでしまうことになる.
以上のような枠組の下でパラメトリックサーチがどのを求めることなしに ， I， (x*) ， …，ん (x*) の l順序だけ(値ように問題 B を解いていくかを見ていこう.今まで B をではない)がわかれば，その中央値を取る z が求まる.

解くために標準的な整列アルゴリズム (O(n logn)) を用

つまり問題 B は部分問題 A: 何本を求めることなしにI , (x*) , ...，fn(x*) をどうやって整列するか ?Jを解くことにより，解けてしまう.この整列問題 A は Ix* がわからなくても任意の 2 つの値 I， (x*) とん (x*) を比較いていたとしよう.そうすると B に対する O(C(n)nlogn)の子聞のアルゴリズムが得られる.

しかしこれではせっかく色々とある性質を全然使いきれていない.
一方 ，P(n) 個のプロセッサを用いて T(n) 並列時間することができる J ならば，その手続きを比較方法としで並列整列アルゴリズムが実行できるとすると，並列アて，適当な整列アルゴリズムに挿入することができる.

ルゴリズムの各ステップでは，高々 P(n) 個の比較を行

そこでx* がわからなくても，1992 年 8 月号

任意の 2 つの値 1，なっている.これを逐次的に l つ 1 つ比較していくかわ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(33)387

りに，一括処理条件を使う方法を考える.すなわち，この P(n) 備の比較に対応する値の中間値を求め，それに関するテストを行なうと，その答から一括処理条件により他の半分の比較の答がわかってしまう.このことを，logP(n) 回繰り返したときには(これは，通常 O(logn) 固に相当するしすべての P(n) 個の比較の答が計算されている.

logP(n) 回実際に比較を行なうので，これ関して全体で O(T(n)C(n)log P(n)) の手聞がかかる.中間値を求める部分については，中央値を求めるための線形時間アルゴリズムを用いる.すると，logP(n)

回の繰り返しで，まず最初の P(n) 個の中間値が O(P(n)) で，以下の P(n)/2 ， … ， P(n)/2i ， …個それぞれの中央値が O(P(n)/2) ， … ， O(P(n)/2 i ) ， …の時間で求まり，全体で O(P(n)+P(n)/2+P(n)/H … )=O(P(n)) の手間ですべての中間値が求まる.

これが並列整列アルゴリズムでの各ステップで行なわれるので，この部分全体で時間 O(P(n)T(n)) かかる.

+T(n)C(n)logP(n)) の手聞がかかることになる.通P(n)=O(nlogn) , T(n)=O (l ogn) や P(n)=O(n) , T(n)=O(logn) が用いられる . C(n)=O(n) やC(n)=O(nlogn) の場合にはれ O(n log2n) ,するのが常套手段である.アルゴリズム設計とかに詳しい人にとっては，この手法で最大限効率が出し切れていないところを見つけるのはそう難しくない.そのようなP(n) {闘の比較を logP(n)回のステップで行なうときに，最初は P(n)/2 個の比較が行なえるのに対し，ステッフ。が進む毎に実質的に比較が実行される数が半減していき，最終的には定数個の比較しか判定していないところである.ただ，これに気がついたとしても，実際に改良できるかとなると，また別問題である.

Cole[3]は，まさしくこのような観点からMegi­

ddo の手法の計算時聞からさらに logn 倍速くできることを示した.この手法では，整列を次のような幅 n/2 ，深さ f(n) の整列ネットワーク上のゲームとしてとらえ，ゲームの終了する(整列が完了する)ステップを見積もる.以下，概略のみ説明する.ゲームは n 個の項目に対以上をまとめると，問題 B を解くには ， O(P(n)T(n)常，改良できるとすると，どこかに最大阪に非効率性があるところは ，このアルゴリズムでは，並列整列アルゴリズムでの各ステップで，前節で説明した Megiddo の手法は，さらに改良できるだろうか?

は効率を出し切れていないところがあって，そこを改良答のわからなかった片方の半分に対して再帰的に繰り返していくと，

3. パラメトリックサーチの拡彊B を解く時聞はそれぞO(nlog3n) となる.

して，整列ネットワーク上で 2 人のプレーヤー(ソーターと相手)によって行なわれる.

2 人のプレーヤーは交互に行ない，まずソーターは相手にいくつかの比較を要求する.すると相手はこれらの比較のいくつかを解く.
ネットワーク上の比較器は，それに対する入力がわかっていて，比較した結果がまだ決定されていない時，アMegiddo[5]はこのような手法が多くの問題に対して有効であることを示している.ここではその内の l つのみ触れておく.他の例についてはこの Megiddo の手法をさらに拡張した Cole の方法を説明した後で示す.

2 種の重みに関してバランスした木を求める問題
グラフの各辺 e 1こ 2 種の正の重み a e とんが与えらクティプと呼ぶ.ゲームの細か L 、ルールを説明しよう.

2 人のプレーヤーは次のことを交互に行なう.
(1) ソーターはアクティブな比較器に重みを割り当てる.
重みの総和(アクティフ重み)を W とする .C を比較器

C に対応する比較とする .c に重み τu が割り当てられている時Clこも加が割り当てられていると考える.

れているとき一般に a e に対する最小重み木とんに関(2) 相手は解いていない比較の重みの総和が少なくともする最小重み木は異なったものになる.この 2 種の重みW/2 になるように重みがついた比較を十分多く行なに関してパランスした最小重み木を求める問題は，線形う.

関数で表わされるような重み We=W e ( え ) =ae+Àb. を新ゲームが終るのは整列が完了した時である.

たに考え ，F(À) で各辺に重み即 e (..ì) のついたグラブの極大木の重みの総和の最小を表わすとすると ，F(ﾀ)=Oの解を求める問題とみなせる.これはこれらの重みに関ソーターの目標はゲームを速く終らせることである.各プレーヤーが 1 回ずつプレーを行なうのを l ステップと数えるとソーターはこのゲームを O (l og n+f(n)) ステップで終する最小比の重み木を求める問題[ 2]に対応する.グらせることができるということを示せる.

ソーターの戦ラフの辺と頂点をそれぞれ E ， V としたときこの問題

略は比較器に次のようなルールで重みを割り当てることは，上記のように並列計算を概念的に用いることによっである.ネットワーク上の深さ J のアクティブな比較器て O(E (l og V)2loglogV) 時間で解くことができる.に重みやj を割り当てる.すると次の補題が成り立つ.

388 (34)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

補題 1k 注 O に対して最初の k+l ステップ後のアクティプ重みは (3/4)k ・ n/2 で押えられる.口補題 2k ミ 5 (j +1/210gn) に対してで定義されるものである.つまり

k+1 番目のステップの閑，深さ j の比較器はアクティプではない.口
補題 2 より引 f(n)+ 1/210gn) ステップ後，アクテそれらの中央値の中の中央値を求めると L 、う問題である.この問題も Megiddo の手法，さらに Cole の改良を用いることにより O(n(log n)2) 時間で解ける.

4. おわりにィプな比較器はない.ということは，すべての比較は解かれ，整列は完了している.したがって，ゲームは O (f(n)+logn) ステップで終了する.

本稿は解説としてはアルゴリズムの中身の話になってしまって，その成果の幅広さ・有用さを述べるところまこの考え方を Megiddo の手法に取り入れて，問題 Bを解く時間 O(n log2n) ,i を固定したとき iから他の点への傾きの中央値を求め，次に i を動かしてO(nlog3n) の中の logn をl つ取ることを考える.相手が比較の半分の重みを解く

では L 、かなかった.ただ並列アルゴリズムの考えを用いて高速な逐次アルゴリズムを構成するというところの面白さまででも，なんとか説明で、きていると幸いである.

ことを求められている時，重みの中央値をもっ比較を解

このパラメトリックサーチの手法の有用さは，大きさく.すると括処理条件によって比較の半分の重みをn の最適化問題があったときに，素朴なアルゴリズムに解いたことになる

比べて n に関して 1 乗(ある場合には 2 以上の)オーダ

n 個のうち重みの中央値をもつもの

は O(n) 時間で求められる.ゲームを行なう時間は，比較を除けば ，O(nlogn) である.

ーの下がったアルゴリズムを提供することにある.

たAKS ネットワーク

だ，この解説中での AKS ネットワークなどの話は，実係数は大きいが O(n logn) 時間で構築でき用的には役に立たないほど定数の大きな話である.今後る [1 J. AKS ネットワークの深さは O(log n) であ

この手法の有用性を実地検証していくことが必要であろり，ここでは O(log n) の比較を行なえばよい.

う.て，0(C(n)10gn+nlogn) 時間となり ， C(n)=O(n)[1J は，に対しては O(n logn) ,0(nlog 2 n) となる.

よっC(n)=O(nlogn) に対しては以下に，この Cole の拡張手法を使って，高速に解ける計算幾何の問題を 2 つを示す.

傾き選択問題 [4J参芳文献[1J M. Ajtai , J. Kom16s and E. Szemer馘i:ognParallelSteps.Combinatorica.
Sortingincl
Vo 1. 3, No.1 (1 983) , pp. ト 19.
[2J R. Chandrasekaran:Minimum Ratio Spaｭ

平面に n 個の点、 (xhYd ， … ， (x削 Yn) が与えられているとし，これらのうちの 2 点を結ぶ N=(~) 個の直線
百 =aijx+bij ， 1~i<fζn を考える.

これらの直線のうち，傾きが h 番目のものを求めたい.つまりnning Trees. Networks , Vol.7 (1977) , pp.335‑
342.
[3J R.Cole:SlowingDownSortingNetworks

S={aij'toObtainFasterSortingAlgorithms. Journala~i く j~n} の k 番目に小さい偵を求めることが問題で

of theAssociation for Comρ uting Machinery ,ある.この問題は， Megiddo の手法によって O(n (l ogVo 1. 34 , No.1 (1 98 7), pp.
200‑208.

Cole の改良を用いることによって log n.S. Salower., W.L.Steigerand[4J R. Cole , Jが取れて O(n logn) 時間で解くことができる.この問

E. Szemer馘i:An Optimal‑Time Algorithmn)2) 時間で，題を解くには，どうしても n(n logn) 時間必要なこと

forSlopeSelection. SlAMJournalonComputｭがわかっているので，これはオーダーに関して最適な結ing , Vo l.1 8, No.4 (1 989) , pp.
792‑810.

[5J N. Megiddo:Applying Parallel Computaｭ

果である.

よりロバストな回帰直線 [6 ]tionAlgorithmsi
ntheDesigno
fSerial Algo ・傾き選択問題に似た問題として，次のように定義されrithms.JournaloftheAssociationforComputing

る回帰直線 (repeated medianregressionline) の傾Machinery , Vo 1. 30 , No.4 (1983) , pp.
852‑
865.

きを求める問題がある.傾き選択問題の場合と同様に，[6] A. Stein and M. Wermann:Finding the

平面に n 個の点 (Xh 仇)，… ， (xn ， Yn) が与えられ，これRepeated 島1: edian R
egressionLine.Proceedings

らのうちの 2 点を結ぶ N=(~) 個の直線 y=aijx+b ij ，ofthe3rd SlAM‑ACMSymposiumonDiscretel~i<j 三三 n を考える.

Algorithms , 1922, pp.
409‑413.

この場合の回帰直線の傾きとは，

â=medimed j 向 aij1992 年 8 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(35)389