譚学厚・平田富夫：計算幾何学入門

概要

本書の副題は「幾何アルゴリズムとその応用」である。章末には練習問題がある。解答はない。

感想

第１章「はじめに」では基本概念とデータ構造について説明されている。その中で、２分探索木についての解説があり、これはデータ構造としての辞書を実現するためのものだ。 現在の言語では辞書そのものが言語の仕様に入っている。たとえば、Python ではそのものずばり「辞書」（ディクショナリ）というデータ構造があり、その他の言語でも、「連想配列」、「ハッシュ」など、 名前はいろいろあるが辞書相当のデータ構造がすでにある。だから、この実現のところは最初は読み飛ばしてもいいだろう。だからといって、データ構造の観点をおろそかにしていいわけではない。 ２章以降で現れるアルゴリズムでは、 そのアルゴリズムに適した固有のデータ構造について言及されているからだ。

p.23 の練習問題 1 では計 11 問が収められている。

1. 平面上に 20 個の点の集合 `S` とその三角形分割をランダムに描く．点集合 `S` の三角形分割はオイラー公式に従うことを確認せよ．

難しい。次の問題に進もう。なお、次の問は本書では (a), (b), (c) のようにカッコがついているが、以下の引用ではカッコを省く。

2. 下のような多角形の例を描け．

1. 凸多角形
2. 凸でない単純多角形
3. 単純でない多角形

SVG を使って次のように描いてみた。

こうやって解答を書いて、疑問が起こる。c の自己交差をしている点は頂点なのか、それとも頂点ではないのか。本書の p.5 を見てみる。

多角形．`E^2` における多角形は，線分の有限集合で以下の条件を満たすものである：(ⅰ) 線分のどの端点もちょうど二つの線分に共有される． (ⅱ) 線分集合のどの真部分集合も条件 (ⅰ) を満たさない．そのような線分を多角形の辺と呼び，端点を頂点と呼ぶ．多角形は，連続する辺以外で点が共有されないとき （すなわち，自己交差がないとき），単純（simple）であるという．（後略）

こうやって定義を書き写していて、自己交差している点は頂点ではないことがわかった。もし頂点だったとすれば、 この自己交差している点である頂点は４つの線分に共有されることとなり、これは多角形の定義(ⅰ)に反する。だから、自己交差している点は、頂点ではない。 c が単純ではないが多角形であるためには、自己交差している点は頂点ではない、としなければならない。

pp.45-46 の練習問題 2 では計 9 問が収められている。

3. 関数 XOR （排他的論理和）を使って関数 intersect() における二つの三角形符号付き面積の乗算をなくせ．

関数 intersect() を引用する。コメントは省略した。

int intersect(struct point a, struct point b, struct point c, struct point d)
{
  int between();
  int area();

  if (between(a, b, c) || between(a, b, d) || between(c, d, a) || between(c, d, b))
    return 1;
  else return (area(a, b, c) * area(a, b, d) < 0 && area(c, d, a) * area(c, d, b) < 0);
}
  

解答は、著者の意図を汲めば次のようになるだろう。

int intersect(struct point a, struct point b, struct point c, struct point d)
{
  int between();
  int area();

  if (between(a, b, c) || between(a, b, d) || between(c, d, a) || between(c, d, b))
    return 1;
  else return ((area(a, b, c) ^ area(a, b, d)) < 0 && (area(c, d, a) ^ area(c, d, b)) < 0);
}
  

変更は、乗算を排他的論理和を表す ^ に変えたことと、これに伴い演算の優先順位を明確にするためにカッコを付けたことである。

その心はこうである。乗算で必要なのは、積が負になるか否かということだけであり、絶対値は問題にしない。 そこで、C 言語で整数が負であるということは整数を 2 進表記したときに最上位ビットに 1 がセットされていることと同値であることを思い出そう。 非負＊非負＝非負であり、これは最上位ビットが 0 どうしの演算結果が 0 になるということである。 他の組み合わせ、非負＊負＝負、負＊非負＝負、負＊負＝非負の組み合わせを考えれば、ちょうど XOR 演算をとった結果の最上位ビットが正負の符号に対応している。 そこで乗算は XOR におきかえることができる。

実は、心配なことがある。ビット単位の演算子を符号つきの整数に対して適用していいのかどうかという疑問である。JPCERT では、 INT13-C. ビット単位の演算子は符号無しオペランドに対してのみ使用する(www.jpcert.or.jp) という記事を出して注意を促している。

わたしとしては、この程度の乗算はケチらずにそのままにしておくのがいいのではないかと考える。このような話は計算幾何学そのものにはあまり関係がないな。

pp.67-68 の練習問題 3 では計 7 問が収められている。

1. 点集合を含む最小面積の多角形（凸とは限らず）がその点集合の凸包ではないかもしれないことを示せ．

これは、練習問題1 の 2. b の私の解答のようなものだろうか。

pp.98-99 の練習問題 4 では計 16 問が収められている。

1. 任意に与えられた 3 点または 4 点のボロノイ図を描け．

難しい。まず、3 点のボロノイ図は、3 点が一般の位置にあるとすれば（3 点が三角形の頂点となっていれば）、2 点どうしの垂直 2 等分線を引けばよい。 このとき、3 直線は 1 点で交わり、これは 3 点からなる三角形の外心である。

誤植としては、p.80 の上から 8 行め、次にたどり着く母点とボロノーイ図とあるが、これは《次にたどり着く母点とボロノイ図》とすべきだろう。 また、同じページの下から 9 行め、逆変換を使って元のボロノ　図とあるが、これは《逆変換を使って元のボロノイ図》だろう。

書誌情報

まりんきょ学問所 ＞ コンピュータの部屋 ＞ コンピュータの本 ＞ 計算幾何学 ＞ 譚学厚・平田富夫：計算幾何学入門