徳山 豪（とくやま たけし）
昭和32年1月22日生まれ
東北大学大学院情報科学研究科システム情報科学専攻 教授
専門： 理論計算機科学・離散数学
昭和54年 東京大学理学部数学科卒業
昭和56年 東京大学大学院理学系研究科数学専攻修士課程修了
昭和60年 東京大学大学院理学系研究科数学専攻博士課程修了、理学博士
昭和61年 日本アイ・ビー・エム株式会社入社、東京基礎研究所研究員
平成11年 日本アイ・ビー・エム社退社、東北大学大学院情報科学研究科・教授
平成10年〜 東京大学数理科学研究科・客員教授
平成11年
【業績】「組合せ幾何学手法を用いたアルゴリズム理論の研究とその応用」
【贈賞の理由】
組合せ幾何学、すなわち、幾何学的データを対象とする組合せ理論は、幾何学的
データや多次元データ処理の基本になる学問であり、多次元データ処理の急速な用
途拡大に伴い、その重要性を増してきている。徳山教授はこの分野において、新た
なアルゴリズムの設計と解析に独創的な結果を得た。今回の受賞の対象となった研
究成果はトポロジカルウォークアルゴリズムとkレベル問題に対する一連の成果であ
る。
情報処理の基本的な処理に、膨大なデータを目的に応じて分割することや必要な部
分を切り出すことがある。これらの処理は、単純な方法では対象数が巨大でなくと
も一般には組合せ数は莫大になり、最高速の計算機をもってしても、計算の困難な
問題になってしまうことが多い。このため、組合せ問題は古くから研究の対象と
なってきた。そのなかでも、データのソート（整列）の問題は最も基本的である。
しかし、幾何学的データ処理では一般にデータの間に自然な大小関係はなく、デー
タを整列するという概念はそのままでは幾何学的データ処理には適用できない。最
も基本的な幾何学的データは平面上の点集合であり、ここでソートに対応する問題
は点集合を直線により分割するデータ分割を管理することである。徳山教授はトポ
ロジカルウォークという概念を提示し、与えられた点集合の直線分割を分割直線を
連続に動かす動作を辿りながら列挙するアルゴリズムを考案した。このアルゴリズ
ムは分割の列挙法として、二次元での自然なソートとみなすことができる。この手
法を用いることにより、二次元の様々なデータ処理を高速化することが可能となっ
た。
kレベル問題は、値の大きい方からk番目までの幾何学的データを切り分ける問題で
ある。組合せ幾何学では、この問題は与えられたn本の平面曲線において、値の小さ
いほうからk番目の曲線の軌跡の複雑度を解析することとなる。この問題は組合せ数
学の代表的な研究者であるロバシュとエルデシュにより1974年に問題が提起され
た。以来、組合せ幾何学の中心的なトピックとして、幾何学的データ処理の困難さ
を象徴するものであった。徳山教授はハイパーグラフ理論を用いた曲線の切断とい
う斬新な手法を用いて、初めて直線族以外の場合の自明でない結果を導いた。この
結果は組合せ幾何学におけるこの分野のその後の急速な発展の原動力となった。