FIT2011 第10回情報科学技術フォーラム

イベント企画

気になる最近の計算幾何学の話題から

【セッション概要】計算幾何学は、1970年代に理論計算機科学の一研究分野として誕生して以来、着実な進歩を遂げてきた。数学出身の研究者が多いことも関係して、理論面の研究に焦点が当てられてきた傾向はあるが、理論だけではなく、計算誤差や縮退などへの対策など、実装面の問題にも真摯に取り組んで来たことも事実である。理論面でも、初期においては連続空間の点集合や多面体を扱うことが多かったが、コンピュータ・グラフィックスへの応用などを考慮して、グリッド平面上で幾何物体を矛盾なく表示する方法などについても様々な角度から研究がなされている。本企画では、応用と離散幾何の面で、気になる最近の計算幾何学の話題を紹介する。

司会：浅野　哲夫 （北陸先端科学技術大学院大学 情報科学研究科 教授）
	【略歴】1977年大阪大学大学院工学博士。大阪電気通信大学講師、助教授、教授を経て1997年より北陸先端科学技術大学院大学教授。VLSIのレイアウト設計自動化、組み合わせ最適化、計算幾何学に関する研究に従事。ACM, 電子情報通信学会、情報処理学会の各フェロー。

9:30-9:40 オープニング （全体挨拶と講師の紹介）
9:40-10:20 講演-1 計算幾何学問題に対する省メモリアルゴリズム
浅野　哲夫 （北陸先端科学技術大学院大学 情報科学研究科 教授）
【講演概要】計算幾何学では様々な幾何計算問題が扱われてきたが、高機能の携帯電話などの普及により、新たな計算環境の下でのアルゴリズム開発も求められるようになってきた。特に、組み込みソフトでは作業用のメモリに対する制約が大きく、省メモリのアルゴリズム開発が強く求められている。本講演では、計算幾何学の幾つかの代表的な計算問題に対する省メモリアルゴリズムの設計技法を紹介する。具体的には、凸包構成問題、デローネイ三角形分割、ボロノイ図構成、ユークリッド最小木構成問題、単純な多角形の内部での最短経路発見手法などを扱う。
	【略歴】1977年大阪大学大学院工学博士。大阪電気通信大学講師、助教授、教授を経て1997年より北陸先端科学技術大学院大学教授。VLSIのレイアウト設計自動化、組み合わせ最適化、計算幾何学に関する研究に従事。ACM, 電子情報通信学会、情報処理学会の各フェロー。
10:30-11:10 講演-2 計算幾何学における離散幾何図形
今井　桂子（中央大学 理工学部情報工学科 教授）
【講演概要】計算幾何学においては、凸包やVoronoi図、Delaunay三角形分割といった幾何学的図形を求めるアルゴリズムやそれらを実際に描いた美しい図形が示されてきた。アルゴリズムの出力を図示することによって確認出来ることは重要であり、また、そこから、また、新しい概念や問題が生まれ、アルゴリズムの開発が進んできた。これまで用いられてきた図形の多くは代数的に表現できるものであることが多い。代数的に表現できない、または、表現できるかどうかわからない図形は離散的に描かなければならない。最近、離散的に図形を描くことによって、距離等分線やゾーン図の理論的研究の動機づけになり、この分野の研究が進んだといえるだろう。本講演では、距離等分線、ゾーン図、非等方性Voronoi図などを題材に計算幾何学における離散幾何図形について眺めてみる。
	【略歴】1985年津田塾大学大学院理学研究科数学専攻博士後期課程単位取得退学。理学博士。東京大学、九州工業大学、津田塾大学を経て、1992年中央大学理工学部助教授となり、1999年から同大学教授。アルゴリズム理論の研究に従事。ACM会員。

11:20-12:00 講演-3 アルゴリズム設計と幾何学：数学の成果を利用したアルゴリズム
徳山　豪（東北大学 大学院情報科学研究科 教授）
【講演概要】アルゴリズムの設計はプログラミングには必須であり、高品質ソフトウエア開発のコアである。 プログラマが短時間で既存知識を用いて良いアルゴリズムを設計するための理論体系を作るのがアルゴリズム理論の一つの使命であるが、そのような体系を作るに研究者の努力とともに、長い年月に蓄えられてきた数学的な技法や知識の利用が必要となる。本講演では、計算幾何学の話題を用いて、長い時間を掛けた数学の研究分野の成果がアルゴリズム設計のためにどのように使われるかを紹介する。特に、掛谷問題と呼ばれる、小学生や一般家庭向きの数学問題（線分の回転問題）を利用し、「数学の研究」の価値を考える。難しい証明は行わないので、数学的な予備知識は必要としない。
	【略歴】1985年　東京大学理学部数学専攻博士課程卒業、理学博士。1986-1999年 日本IBM東京基礎研究所で理論計算機科学の研究に従事。1999年より 東北大学大学院情報科学研究科教授。アルゴリズム理論の研究と応用を専門とする。情報処理学会フェロー。