アルゴリズムクイックリファレンス 第2版

280

■

9

章 計算幾何学

9.1

 問題の分類

計算幾何学問題は、本来、点、線、多角形といった幾何学的対象を扱う。計算幾

何学問題は、

(a)

処理される入力データ、

(b)

行われる計算、

(c)

処理が静的か動的か、

によって分類定義される。

9.1.1

 入力データ

計算幾何学問題は入力データを定義しなければならない。一般的に処理される代

表的な入力データを次に挙げる。

●

2

次元平面にある点集合

●

平面上の線分集合

●

平面上の長方形の集合

●

平面上の多角形の集合

2

次元構造（線、長方形、円）には、対応する

3

次元構造（平面、立方体、球）があ

り、さらには

n

次元構造（超平面、超立方体、超球体など）がある。高次元を含む例

には次のようなものがある。

マッチング

eHarmony

お見合いサービスは、適合性マッチングシステム（米国特許

番号

6,735,568

）を用いて

2

人の長期的相性を予測する。システムの全利

用者（

2015

年で

6

千

6

百万人と推測される）は、

258

項目にわたる対人関

係尺度質問に答える。すると、

eHarmony

は、

29

次元データに基づいて

2

人の間の近接度を決定する。

データ補完（Dataimputation）

ある入力ファイルには

1

千

4

百万のレコードがあり、各レコードは文字

列または数値の複数のフィールドからなる。これらの値の中には、間違っ

ていたり、欠落しているものがある。怪しいレコードに「近い」他のレコー

ドを見つけることによって、怪しい値に対する「訂正」を、推論または補

完できる。

本章では、計算幾何学での核と ...