歴代受賞者一覧

受賞者紹介

徳山　豪（とくやま・たけし）
昭和32年1月22日生まれ
東北大学大学院情報科学研究科システム情報科学専攻　教授

贈賞の理由

組合せ幾何学手法を用いたアルゴリズム理論の研究とその応用

組合せ幾何学、すなわち、幾何学的データを対象とする組合せ理論は、幾何学的データや多次元データ処理の基本になる学問であり、多次元データ処理の急速な用途拡大に伴い、その重要性を増してきている。徳山教授はこの分野において、新たなアルゴリズムの設計と解析に独創的な結果を得た。今回の受賞の対象となった研究成果はトポロジカルウォークアルゴリズムとｋレベル問題に対する一連の成果である。

情報処理の基本的な処理に、膨大なデータを目的に応じて分割することや必要な部分を切り出すことがある。これらの処理は、単純な方法では対象数が巨大でなくとも一般には組合せ数は莫大になり、最高速の計算機をもってしても、計算の困難な問題になってしまうことが多い。このため、組合せ問題は古くから研究の対象となってきた。そのなかでも、データのソート（整列）の問題は最も基本的である。

しかし、幾何学的データ処理では一般にデータの間に自然な大小関係はなく、データを整列するという概念はそのままでは幾何学的データ処理には適用できない。最も基本的な幾何学的データは平面上の点集合であり、ここでソートに対応する問題は点集合を直線により分割するデータ分割を管理することである。徳山教授はトポロジカルウォークという概念を提示し、与えられた点集合の直線分割を分割直線を連続に動かす動作を辿りながら列挙するアルゴリズムを考案した。このアルゴリズムは分割の列挙法として、二次元での自然なソートとみなすことができる。この手法を用いることにより、二次元の様々なデータ処理を高速化することが可能となった。

ｋレベル問題は、値の大きい方からｋ番目までの幾何学的データを切り分ける問題である。組合せ幾何学では、この問題は与えられたｎ本の平面曲線において、値の小さいほうからｋ番目の曲線の軌跡の複雑度を解析することとなる。この問題は組合せ数学の代表的な研究者であるロバシュとエルデシュにより1974年に問題が提起された。以来、組合せ幾何学の中心的なトピックとして、幾何学的データ処理の困難さを象徴するものであった。徳山教授はハイパーグラフ理論を用いた曲線の切断という斬新な手法を用いて、初めて直線族以外の場合の自明でない結果を導いた。この結果は組合せ幾何学におけるこの分野のその後の急速な発展の原動力となった。

※所属名および役職は、受賞時のものです。