デジタル平面の計算幾何学

摘要

計算幾何学は、幾何的なデータ、たとえば平面や空間内の点集合や多角形、多面体を効率的に処理するアルゴリズム理論として発展してきた。アルゴリズム設計には永い数学の歴史で培われた幾何学の定理や手法が用いられ、ユークリッド幾何学を主体に、近年では微分幾何学、位相幾何学、代数幾何学なども、アルゴリズムの解析に利用されている。一方、計算幾何学に直結して成長した幾何学としては組合せ幾何学があり、計算幾何学の深い理論には必ずといっていいほど組合せ幾何学での新しい発見が関係している。また、マンハッタン距離空間なども計算幾何学特有の幾何構造である。 もちろん、これら既存の幾何学を探求することも重要であるが、計算のための新しい幾何の構築の可能性を探ることは、分野の大きな発展を呼ぶはずである。 計算機の本質から、実際にわれわれが扱うのは連続体上の幾何対象ではなく、デジタルデータで幾何学を表現したものである。本講演では、もう一つの新しい幾何学として、デジタル平面やデジタル空間を直接扱う幾何学問題と、そこで生じる新しい幾何学の課題について紹介する。