A03班の目的は, 幾何に関係する諸問題を効率的に解決するアルゴリズムを開発することと, それらの問題の本質的な計算困難さを解析することにより, 近似アルゴリズムの妥当性を示す ことにある. 直接的に幾何データを取り扱う問題だけではなく, 入力は幾何に関係がなくても, 解決の手段として幾何的な取り扱いが有効である場合もあり, その守備範囲は広範である. 研究テーマが広範囲にわたることから、ともすると個人研究の集まりになりがちであるので, 班全体での共通の方向を定めて積極的に共同研究に取り組んでいる.もちろん,班の中で 閉じた形での共同研究にならないように,積極的に他の班のメンバーに声をかけるだけでなく, 特定研究の範囲を超えてディスカッションに参加してもらっている.一つの試みは, 一見したところ計算幾何学と無縁ではないかと思われる画像処理の分野での貢献を探る ものである.これについてはテーマ別研究会の欄で詳しく触れているが,A03班からの 参加者が多かったので,ここに記しておく.
共通の技術的基盤を確立するためにA03班ではアルゴリズムの記述に 適したLEDAに焦点を当て, できる限りLEDAでアルゴリズムを記述しようとしている. 昨年はドイツよりProf. Mehlhornを招いてLEDAに関する講演会を開催し,多数の注目を 集めたが,今年は本特定研究の費用でLEDAの主開発者であるProf. Naeher (ドイツの Trier University)を日本に招待し,さらに実質的な作業を推し進める予定である.
A03班の浅野と徳山が中心となって進めている研究にディジタル・ハーフトーニングの
研究がある.これは画像を限られて色数で美しく出力するための技術であるが,
これを最適化問題として定式化したとき,様々な問題がアルゴリズム工学と関係する
ことが判明した.まったく思いがけない理論成果がこの技術に利用できることが
わかってきたので,今年中に計算機実験を行って実際的な評価も行う予定である.