"""""'/1111111/1/1/1/1/1/1/'/"""'/1/1"""'"""""""".

,.,.,."""".,.,.,.""".,.,.,.,.1 ,.'."", IJJIIJJJJJJJJ/J/JIJJJIIIJJIIIJIIIII'JJJJJJJIJJJIJJIIIIIIIIIIIIJIJIJJJJIIIIIIIIIIIIIIIIIIIIIIJIJIIIJJJI111I11111111111

受賞論文要約

学生論文賞

111111111111111111111111111111111111111111111111111111111111111111111111/""11111111111111111111111111111111111111111/1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111/

Voronoi 線図の効率的構成法に関する研究
東京大学大学院工学系研究科情報工学専門課程現在(財)電力中央研究所

伏見正則助教授)

(指導教官

大屋隆生

111111111111/1111111111111/111111111111111111111111111111111111111/1111111111111/11111111111111111111111111111111111111111111111111111111111111111111/ ・ 1111'111"11111/111'11""'1'11111""'1'1'11'111111111'111'11111111111111111111I

Vη (Pïlはじめに(i出 1 ，. ..， n) による平面の分割 Vn である.

Voronoi線図の構成法としては，最悪の場合の計算量

Shamos[4J 以来，幾何学図形の計算機アノレコリズムをが o (1l 1ogn) の再帰二分法 [5J と o (n 2 ) の逐次添加被う計算幾何学の分野が確立されたが，その中心課題の法 [IJ が知られている.本論文において提案する逐次回分ひとつとして Voronoi 線図がとりあげられている.ま

添加法は，逐次添加法における添加順序を四分木を用いた， Voronoi 線図は地理情報処理，都市計画，生態学，て定めたものであり，平均的な計算量が母点の数 n に比画像処理，数値計算法などの幅広い分野に登場する.

例するように改良されている.

Voronoi線図とは平面上にいくつかの母点が与えられたとき，平闘を各母点をひとつだけ含む領域(勢力圏)に逐次添加法分割するものであって，各領域のどの点もその属する領逐次添加法は ， m 個の母点 P i (i=I ，...， m) から成域の母点のほうがそれ以外の母点、より近いように分割l さる Voronoi 線図 V悦に新たにひとつの母点 P隅刊を添れたものである.数式による定義は次のようになる.

加して V m + 1 を作る操作を繰り返す方法である.

平面上に n 個の点(母点 )られたとき ，Vη (Ptl

Pi (i=I ，...， n) が与え

P i の“勢力闘 " (Voronoi 多角形とよぶ)

母点

P m +1 の添加に必要な操作は以下のとおりである:(1) Pi (i=I ，...， m) の中で P叫刊に最も近い点を求める(点位置決定とよぶ).とは，(II) Pm+l の Voronoi 多角形を求め ， V叫のうち P刑判
Vn(Pz)=q{Pld(P ， Pz)ζ d(P ， P j )}の Voronoi 多角形の内部を消去する(図 1 ).

(d:EucJ
id距離)で定義される. Voronoi 線図とは，••(1)は，母点 P i (i=I ，...， m)のうちの適当な母点(出発点とよぶ)から始めて ， V m において Voronoi 辺を共有する母点の中から P m +1 により近い母点を探すことを繰り返す.その際できるだけ P m +1 に近い母点、を出-/・•

発点、に選ぶ必要がある.また( II)では ， Pm+l の近傍の母点のみが計算の手間にかかわるのでP間 H の近傍の母点分布の相似性を保つようにすれば，各段の( II)の平均的な手聞は m と無関係になる.
以下で、は母点が正方形内に分布していると考える.まず，次のような逐次添加法における工夫が考えられる.
日をパラメータとして k=La .v iiJ と定め，正方形の各辺を k 等分しでか個のセルを作り，母点をセルに振り分ける.が個のセルにあらかじめ(たとえば図 2 の spiral
巻出し順のように)順番をつけておき，その順にしたがってセル内の母点をとり出して添加を行なう.その際，
図 1

母点の添加にともなう修正

実線は・印の)，lX の集合の Voronoi 線開，は添加した点企の Voronoi 多角形
1984 年 l 月号

点位置決定の出発点としては，直前に添加した母点を用
破線

L 、る.この工夫により逐次添加法の平均的な計算量は何もしない場合に比べて減少するが点あたりの計算時© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

61k1.00.
8

L一u6~‘Nh\ωE

記,,/"

/ιJ

J//"

け.， !I2

図 2spiral 巻出し順

•
•‑

リ .26

聞は n とともに増加する.

(~4 参照)0.22. 逐次回分添加法

27

逐次回分添加法は，逐次添加法において母点の添加順28うに定めたものである.ここで四分木の葉は単位正方形

0 2ll
21

2 24 2"•21
1
3 21numberofgenerators fl序および点位置決定の出発点を四分木を用いて以下のよを 4 M 等分したセノレに対応し，深さ h の節点、は単位正方

29

図 3

各種算法による 1 点あたりの CPU 時間..，:再帰二分法・:逐次添加法(工夫なし)・逐形を 4 K 等分した正方形 (= 4K-M 個のセノL の合併)を次添法 (Spiral 巻出し 11頃)

表わし，深さ k+l の節点 4 個の親である.

・:逐次回分添加法(1 )α をパラメタとして M= Llog ， (a 2 n)J と定め，正方形の各辺を 2 M 等分して ， 4 M 個のセノレを作り，母点をセノ L に振り分ける.

m:=2m; u:=‑2u; S:=S 十 u(2) 四分木の葉 r に対応するセノレ(l(r) ，J(r)) を以下の手順により定める.

(3)

c:=L2M /3J;I(O):=C;J(O):=C;
u:=( ー 1 )M; m:=I; r:=O;S:=2c+u;

fort:=1toM do

セル(=四分木の葉)を番号順に探索し，母点が含まれていれば，任意に l つを選んで，その葉の空の祖先の節点すべてにその母点を書き込む.
(4) 四分木の根から幅優先(breadth -first;

ただしbegin同じ深さの節点は右側優先)で木の節点を調べ，未for ρ:=1 tom do

添加の母点が含まれていれば，その母点を添加す

begin

る.点位置決定の出発点としては，その節点、の親のr:=r+l;l(r):=S‑l(r‑m);

節点に書き込まれている母点を用いる.

J(r) ・ =J(r-m)

3. 計算機実験

end;
m:=2m;

本論文で提案した逐次四分添加法の効率を従米の再forρ:=1 tom do

62end

帰二分法，逐次添加法および工夫を加えた逐次添加法

begin(spiral 巻出し順)と比較するため，正方形内にランダ

r:=r+1;
I(r):=l(r‑m);

ムに一様分布する n 個の母点に対する Voronoi 線図 V nJ(r):=S‑J(r‑m)

を構成するための CPU 時間 /n を図 3 に示す. (図中のプend;

ロットは 10組のパターンに対する平均値を示す;東京大© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

学大型計算機センタ- HIT
A CM-280H , VOS3/JSS4 ,最適化 FORTRAN77 ，

参芳文献

OPT=2 による)他の算法では 1 点あたりの計算時間が n とともに増加[1] Green. P.J. and Sibson , R.:Computing

するのに対し，逐次四分添加法 (a=!) では川こよらず

DirichletTessellationin the Plane.に O.26ms 程度である.なお，Computer Journal , Vol.21 (1 978) , pp. 168‑Voronoi 線図を表現するためのデータ構造としては標準的データ構造 [2J を用いた.逐次回分添加法のパラメタとしては α=1 がよいこと，また逐次回分添加法は母点分布の非一様性に対しでも十分頑健なことが計算機実験により確かめられた.

The

173
[2J 伊理正夫，他:地理的情報の処理に関する基本
アルゴリズム.日本 OR 学会報文集，[3J Ohya ,T. ,1983Iri , M. and Murota ,K.:

Improvements ofthe Incremental Method

さいごに

fo
rthe Voronoi Diagram with Comparison

逐次四分添加法は，平均的な計算量が母点の数 n に比ofVariousAlgorithms. Submitted toJournal

例する程度にまで改良されており，母点分布の非一様性

oftheOperationsResearch Societyof Japanに対しでも十分頑健であるから，実際的な算法として推奨される

紙面の都合で詳しくはふれることができなかったが， Voronoi線図を表現するデータ繕造としては，[4J Shamos, M. 1.:Computational Geometry.
978Ph. D. Thesis , Yale University , 1[5J Shamos , M. 1. and Hoey , D. :Closestpoint

計算時間の短さ，プログラムの書きやすさ，汎用性の観

Problems. Proceedings ofthe16th Annual

点から，記憶領域を節約した Horspool のデータ構造よIEEEりも，標準的デター構造がよい[3].一般化 Voronoi 線

Computer Science , New York , 1975 , pp
.151‑図 [2J や，多次元 Voronoi 線図においても逐次添加の手162Symposium on

Foundations of法を用いることができると予想される.

íOR 事例集 j 発行について
1975 年，1FO RS 東京・京都大会の頃発刊されたことができ，重大なヒントを得られることでしょう.

íOR 事典」は本学会の社団法人化記念の意味もあり本書はまた大学等での教材や研究テーマの発掘にも役会員諸氏の全面的ご協力のもとに完成したものでし立てていただけるでしょう.もっぱら理論面の研究をた.昨年創立 25 周年を迎えた本会は，その記念事業のしている方々にもご一読をおすすめいたします.

l っとして íOR 事典 I 増補を企画いたしましたが事例 1/2 ページの分量で書かれていますので，それは íOR 事例集 I としてこのほど実現いたしまし手

短かに問題点や解決の方針などを知るには便利です.

た .rOR 事典 J 同様，広く会員諸氏のご協力をいただ

もっと詳しい情報を得たいと思われた方は，原論文をきましたので，すでに多くの会員はご存じかと思いま

読むなり著者に問 L 、合わせるなりしていただければよすが， í 日本オベレーションズ・リサーチ学会編」と銘いのです.

打った出版物としては最初のものです.

信しています.ぜひ，会員各位の座右に 1 冊を備えら

本書は rOR 事典 J 事例編の増補版とし、う性格上，編集のスタイルも同ーのまま

rOR 事典」発刊以降に{舌用次第では大変な情報源になりうると確れてご活用ください

そして，周囲の方に々もご宣伝ください.それは OR の事例をもっと増やし，OR を発表された OR の事例 375 編を集めたものです.それ広めることにつながります.その結果，次の数年後にはこの 8 年間の OR 発展の足跡をみごとに物語っていはもっと立派な íOR 事例集 j が作られることでしょます.

う.会員の皆様のご協力をお願 L 、 L 、たします.

分類は主として企業活動の諸局面によっていますから，たとえば生産計画の問題を抱えている方は，他の・ B6 版214 ページ，日科技連出版社，方が類似の問題をどのように解決したかを容易に知る・学会事務局でも取り扱っております.

1984 年 l 月号

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

2400 円63