計算幾何学 |
作成日：2000-05-07 最終更新日： |
古典的で基本的な幾何学対象として、点、線分、（半）直線、円、多角形などがある。 これらの対象の関係で述べられる問題を解決するために、 コンピュータで扱うのに効果的なアルゴリズムとデータ構造を研究する学問を計算幾何学という。
以下、よく出てくる定義と読み方を示す。 本によっては原語でのみ与えられ日本語としての読み方が不明なものが多いので、 その整理も兼ねている。
ドロネー図とも呼ばれる。 距離空間内に離散的に分布した点の集合に対し得られる、それらをある方法に従い辺で結んだ図形。
与えられた点の集合に対して、それらの中で最も近い点に代表される部分に属するように空間を分割する図形。
私は数学が好きだったが幾何学は苦手だった。計算機で図形が扱えればいいなとずっと思っていたので、 計算幾何学と言う名前を聞いた時はわくわくしたものだ。とはいえ、学問であるから 難しく、どんなことも大変なのだなあというごく当たり前の印象をもった。
薄い本だが、計算幾何学の基本的な考え方はしっかり記述されている。 この本の 44 ページに、「直観だけではうまくいかないのも、離散・計算幾何の奥深いところでもある」 とさりげなく書かれている。この一文を見るだけでも、素人は近付かないのがいいのだろうか。 題材には、「画廊定理」という、優雅な名前をもつものも紹介されているだけに、 落差が一層際立つ。
最初に計算幾何学関係で手に入れたのがこの本だった。 私はこの本を十分の一も理解していないが、 アルゴリズムの不思議さについてだけは分かった気になっている。 なので、この本になぜか載っていた、計算幾何学とは直接の関係がない（と思う）、 あるアルゴリズムについて感想を述べる。
n 個の数の中で k 番目に大きな要素を求める速いアルゴリズムが紹介されているのが、 他のアルゴリズムの教科書にない、珍しい物だと思う。 なんだか難しいことが記述されていて、学者とはとかく難しいことを考えたがるものだという、 妙な感想しか出てこなかった。事実、このアルゴリズムは「悪魔のように巧妙な」という形容詞が ついているのをどこかで聞いたことがある。 それで、このアルゴリズムが実際に役に立つかどうか、少し考えてみた。 このアルゴリズムは、「15 個のデータのソートには 42 回の比較で十分であることが知られている」 という事実に基づいて組み立てられている。この「」内の事実をどのように証明するのだろうか。 ずっと気になっていたのだが、今回この稿を書くにあたって Knuth の本を調べてみた。 さすが Knuth 、この事実について詳しく調べていた。なんだか妙な図式（ダイアグラム）を書いて 漸化式を導出していた。ならば、本当なのだろう。では、 高々 42 回の比較でソートを完了するプログラムはどのようなものだろうか。 そこまで Knuth の本にはなかった。 きっと、「」内を実装したプログラムはないのだろう。そして「悪魔のように巧妙な」プログラムも 役に立たないのだろう。最後に、石畑清が書いた「アルゴリズムとデータ構造」の中からの一文を引用する。 「整列のため比較回数の下限を n の値それぞれについて調べる研究がある。（中略） ただし、このような最小手数の整列法を実際のプログラムに利用することはまずない。（後略）」
Fortran 77 で書かれたプログラムにより、 計算幾何学の各種問題をプログラミングしている。サブルーチンの使い方に一貫した姿勢が見られ、 気持ちがいい。
こちらはスマートな、工学を意識していない計算幾何学である。 こうなると役立つ役立たないをうんぬんするのはばかげているくらい、観賞用の数学になっている。 もちろん、この本で言及されている Vapnik-Chervonenkis 次元は、パターン認識という工学の一領域について 非常に大事な概念であることは私にも分かっているのだけれど。
計算幾何学の、否幾何学の一番基本的なことが載っているのがこの本である。 たとえば、三角形の外接円の中心と半径はどのようにして求めるか、ということは いざ聞かれると困ってしまうのだ。こういったことが整理されている。 もちろん、高度な話題も載っているのだが、内容が古めである。
計算幾何学の中で最近出た本である。訳者もいっているとおり、注目すべきは 確率的アルゴリズムに関する著述が多いことだろう。この本のアルゴリズムを 実装する必要が出てきそうだったこともあって、私は計算幾何学の各種アルゴリズムを どのようにして実装するかという工学的な観点に興味が向いている。 杉原先生の本のように Fortran を使ってもいいと思う（しかし Fortran 90 に すべきだとは思う）。しかし、データ構造があまりにも貧弱である。 悪名高い C++ を使って実装しようと試みている。C++ の STL を使えばそれなりの 効率と保守性が達成されるのではないかと思っているからだ。
理論的な側面を徹底的に追求した本である。著者は「天才」と呼ばれているらしい。
第1部 組合せ幾何 計算幾何学における基本概念 点配置の順列表現 点配置の構造 点集合の分割 アレンジメントにおけるゾーン 複数のセルの複雑さ) 第2部 基本的幾何アルゴリズム アレンジメントの構成 凸包の構成 アレンジメントの骨格 線形計画法 平面における点位置決定 第3部 幾何的アルゴリズムの応用 点配置とアレンジメントに関する問題 Voronoi図 平面での分離と交差 アルゴリズム設計のパラダイム
まりんきょ学問所 ＞ コンピュータの部屋 ＞ コンピュータの本 ＞ 計算幾何学
