近年の計算機の高性能化に伴ない,計算の対象として数値や文字データに限らず図形や画像データまでも含まれるようになり,計算機の利用分野は飛躍的に拡大しつつある.そのような時代背景を受けて,幾何的な構造を有する情報を計算機で高速に処理するアルゴリズムに関する研究が,計算幾何学という名の下に,この20年ほどの間に極めて精力的に行なわれ,多くの成果を上げてきた.しかし,それらのアルゴリズムは計算誤差が発生しないという仮定のもとでのみ正しさが証明されたものであるため,計算機プログラムに翻訳すると計算誤差のために正しく動作しないことがある.この問題は,単にアルゴリズムをプログラムに翻訳する際の間違いであるといったレベルの問題ではなく,理論と現実のギャップに根付く深刻な問題なのである.最近になってこの問題の深刻さが次第に認識されるようになってきた.

　本論文では3次元Voronoi図を対象とし,これを構成するアルゴリズムの数値的安定化を試みた.Voronoi図は,与えられた有限点集合(各要素を母点という)に対して,距離の概念に基づいて,各母点の勢力圏分布を求めたものである.3次元のVoronoi図は,空間の多面体分割を与え,空間内の補間,点パターンの解析,3次元有限要素法のためのメッシュ生成,3次元図形の薄面化,骨格線抽出,ロボットの衝突回避作業計画など多くの応用をもつ.

　3次元Voronoi図を構築するアルゴリズムは,いくつか提案されているが,実用的に最も効率がよいものの一つに逐次添加法がある.これは,数個の母点に対するVoronoi図から始めて,母点を一つずつ添加しながらVoronoi図を逐次更新していく方法である.ここでは,この逐次添加法を基に,"位相優先法"とよばれる手法に従って,数値的安定化を計る.

　逐次添加法をはじめとする従来のアルゴリズムでは,母点同士が特殊な位置関係(退化とよばれる)にあるとき,またはその状態に近いとき,計算誤差が原因で処理が破綻する危険性が高い.これらのアルゴリズムが破綻するのは,誤差を含んだ数値計算結果を信用し過ぎるためであることを反省し,位相優先法においては,計算誤差を含む数値判定より幾何図形の持つべき位相構造の保持を優先させることにする.そこでは,数値計算を絶対的なものとして信じることをやめ,計算誤差の影響を受けない組合せ計算を処理の中心におく.そのために,アルゴリズムの骨格を位相構造の変化として記述し,位相構造に矛盾をきたさない範囲で最も確からしい解を選ぶためにまたそのためだけに数値計算結果を利用することにする.

　提案されたアルゴリズムは計算機へ実装され,計算機実験によりその振舞いが観察された.その結果,従来の算法ではほとんどの場合に処理が破綻をきたすような悪条件の入力に対しても,位相的に矛盾のない結果が出力されることが確かめられ,その数値的安定性が実証された.例えば,球面上にランダムに配置された100個の母点に対して出力されたVoronoi図を図1に示す(交差立体視用の表示を行なっている).この場合には,すべての領域が,球の中心に集まり,著しい退化状態になっている.この中心付近を3×10⁷倍に拡大してみたのが,図2である.これを見ると,中心付近は真のVoronoi図とはかなりかけ離れていることがわかる.しかし,位相的には矛盾のないことが理論的に保証されているため,間違いのない数値判定をすることがほぼ不可能な状況においても,処理が最後まで実行されるのである.

図1.著しい退化を生じる母点配置に対して出力された3次元Voronoi図

図2.中心付近の拡大図

　その後,様々な入力に対する計算機の出力結果を検討していくうちに,3次元Voronoi図とその双対図形である3次元Delaunay図において,構成の困難さに違いがあることがわかってきた.3次元の場合には,Voronoi図に比べてDelaunay図のほうが数値誤差による影響が表面化しやすく,Voronoi図の小さな乱れが,Delaunay図では大きく拡大されて現れるのである.このことは,理論的な議論の段階では認識できず,計算機実験によって初めて明らかになった知見である.この問題に対しては,位相的な処理のみでは対処できず,計量的なチェックを加えることで対策を講じている.

　また,位相優先法のもつ数値的安定性は思わぬところにも効力を発揮した.それは,位相優先法を適用して設計された3次元Voronoi図構成算法を利用すれば,その骨格となる位相的処理を全く修正することなく,数値判定部のみの変更によって,制約つき3次元Delaunay図の近似構成にも適用できるのである.制約つきの3次元Delaunay図とは,あらかじめ指定されたいくつかの面を必ず使用しなければならないという制約のもとで一般化されたDelaunay図である.そこでは,位相優先法の大きな特徴である「どんなに計算誤差が生じようとも位相的には矛盾のない解を出力する」という性質を積極的に利用し,数値判定結果をねつ造することで,制約となっている面が使われるような位相構造を意図的に出力させている.当然,その結果得られる出力は正しいVoronoi図からははずれたものになっているが,位相的性質は満たされているため,その双対図形を作ることはできる.そして,それが指定された面をすべて使った制約つきの3次元Delaunay図になっているのである.

　このような手法が可能であるのは,位相優先法を適用して設計されたアルゴリズムにおいては,Voronoi点の座標値などの計量的なデータは,位相構造から決まる二次的なデータとして扱っているので,その値が正しいものでなくとも,処理が破綻することなく,位相的には矛盾のない結果を出力するためである.

　最後に,3次元Voronoi図の応用例として,有限要素法におけるメッシュ生成をとり上げる.そこで利用されているメッシュには,格子が規則正しく並んでいる構造格子と,規則性を要求しない非構造格子がある.これまでは,メッシュ生成の容易さから構造格子がよく利用されてきたが,複雑な形状に対応するために,格子の並びに制約がない非構造メッシュが望まれるようになってきた.そして,この非構造格子を生成するための手法の一つとして,Delaunay図を使った方法が提案されている.Delaunay図を利用すれば,望みの密度に応じて領域内に母点を配置することにより,分割の密度をたやすく調整することができるので都合がよい.しかし,従来のアルゴリズムでは数値誤差の影響を受けやすく,実用に耐え得るシステムを構築できない.

　そこで,位相優先法に基づいて数値的安定化が計られた3次元Voronoi図構成算法を利用して,Delaunay図による四面体メッシュ生成実験を行なった.実験では非常に大きな密度差のある母点集合を入力として与えたが,その場合においても四面体メッシュの生成が安定して行なわれることが確認された.

　ただ,有限要素法においては解の精度を上げるために,各メッシュの形状が問題になってくる.ここでは,細長い領域や平らな領域がなるべくできないようにするために母点の再配置を考える.そのため,Delaunay図の位相構造を利用して,各母点をそれに隣接する母点の重心の位置へ移動させ,こうしてできた新しい母点配置に対して,再度Delaunay図を求め直した.その結果,全体的にはかなり形状が改善されたが,依然として平たい四面体が残ってしまうこともわかった.この点に関してはさらなる検討が必要である.

　以上のように,本論文では,位相優先法を適用して数値的安定化を計った3次元Voronoi図構築アルゴリズムを提案するとともに,多くの計算機実験によりその有効性を実証してきた.そして,その実験過程においては,設計段階では考えつかなかったいくつかの重要な知見を得ることができた.

　幾何学的情報の計算機処理技術は,地理情報処理・コンピュータグラフィックス・パターン認識・有限要素法・ロボティクスなど広範囲な応用場面から望まれており,それに答える形で種々のアルゴリズムが開発され,計算幾何学とよばれる一つの理論体系をなすに至っている.しかしこの体系は,数値計算は誤差無く行なえるという前提の上に成り立っているため,有限の精度で計算の行なわれる現実のコンピュータでは,それらのアルゴリズムが必ずしも正常に動作するとは限らない.コンピュータの上で安定して動作するアルゴリズムの構築は,実用上重要な課題として残されている.

　本論文は,このような背景のもとで,計算幾何学の基本的な対象の一つである3次元Voronoi図を取り上げ,数値誤差が発生しても安定して動作する幾何アルゴリズムの設計方法を研究したもので,「数値的に安定な3次元Voronoi図構成算法とその応用」と題し,序章,本論5章,終章よりなる.

　「序章」では,幾何アルゴリズムを数値誤差に対して安定なものに改良するために今まで提案されている諸手法をまとめることによって本研究の位置づけを与えたあとで,以下の各章の概要を述べている.

　第1章「Voronoi図とその構成算法」では,Voronoi図とその双対図形であるDelaunay図を定義し,その性質を論じたのち,Voronoi図を構成するための代表的算法の一つである逐次添加法についてまとめている.この算法は,誤差は生じないという仮定の下で計算時間の短縮をはかったもので,本論文での数値的安定化の対象となる.

　第2章「3次元Voronoi図構成算法の数値的安定化」では,従来の逐次添加法を数値的に安定なものに改善する一つの方法を提案している.改善のための基本方針は位相優先とよばれる考え方である.これは,対象がもつべき組合せ位相的性質に着目し,少なくともその性質を満たすようにアルゴリズムの基本部分を組合せ計算だけで記述することによって,誤差から生じる矛盾を回避しようというものである.ここでは「それぞれの母点は空ではないVoronoi領城をもつ」,「Voronoi領域は単連結である」,「二つのVoronoi領城は高々1個の境界面を共有する」の三つの位相的性質に着目している.そして,Voronoi図の更新過程においてこれらの性質を保持するための効率のよい監視機構を提案している.さらにこの提案をプログラムとして実装し,退化したVoronoi図も安定に構成できること,安定化を施しても従来の算法がもっていた計算量が劣化しないこと,数値計算結果に人工的な誤差を加えても位相的矛盾は生じないことなどを計算実験によっても確認している.

　第3章「3次元Delaunay図の構成」では,第2章で構成した算法をDelaunay図の計算に応用している.Delaunay図はVoronoi図の双対図形であるから,理論的には一方から他方を作ることは容易である.しかし実際には,位相的性質が保証されたもとでの数値的乱れが,3次元ではVoronoi図よりDelaunay図の方が大きいという新しい事実を指摘し,その理由を理論的に解明すると同時に,この乱れを防ぐための数値的工夫も提案し,その有効性を実験でも確かめている.

　第4章「制約つきDelaunay図の近似構成法」では,制約が与えられた場合のDelaunay図の構成法を考察している.第2章で作ったVoronoi図構成算法では,どれほど大きな数値誤差が発生しても,出力の位相的無矛盾性は保証されている.この性質に着目し,与えられた制約が満たされるように数値を変更するという方針によって,ほんの少々のプログラムの変更で制約に対処できることを指摘し,その有効性を計算実験で確かめている.

　第5章「3次元メッシュ生成への応用」では,有限要素法のためのメッシュ生成法を考察している.制約つきDelaunay図構成算法を利用して,点の密度に大きな差のある場合でも四面体分割が安定して構成できることを示し,さらに,得られた四面体をよりふっくらしたもの(有限要素法に利用したとき誤差の生じにくいもの)にするための点の位置修正法を提案している.

　「終章」では本論文の成果を要約し,今後に残された課題についてもまとめている.

　以上を要するに,本論文は,従来の3次元Voronoi図の構成アルゴリズムに,位相優先の考え方に基づいた数値的安定化を施して実用的ソフトウェアを作成し,それをいくつかの実際的問題に応用したもので,数理工学および情報工学の発展に大きく寄与するものである.よって本論文は博士(工学)の学位請求論文として合格と認められる.