応用分野の広い幾何学アルゴリズムとデータ構造

「コンピュータ・ジオメトリ ――計算幾何学：アルゴリズムと応用――」（M・ドバーグ他著、浅野哲夫訳、近代科学社、2000）を読みました。点や線、多角形といった、幾何学的なデータを扱うためのアルゴリズムとデータ構造の本です。

本書では、CG や GIS など、幾何学と直接結び付く応用のほかにも、データベースの検索など、データを幾何学的に解釈することで、計算幾何学分野のアルゴリズムが応用できることも示されています。例えば、身長と体重のデータがあったとすると、それを2次元平面上の点と見なせば、身長・体重が特定の範囲にあるデータを素早く求めることができる、といった具合です。

各章で紹介されている方法を見ると、木構造を活用する例が多く見られます。私は今まで1次元データを扱う木構造しか知らなかったので、本書に出てくるような2次元以上の多次元データも扱える木構造はとても新鮮でした。

また、言語に依存しない範囲でアルゴリズムも具体的に書かれています。そのため、今後も長く使える本だと思います。