特定領域研究
「新世代の計算限界」 ニュースレター 第 2 号 2005/3/8
はじめに
このニュースレターは，特定領域・新世代の計算限界のメンバーの情報交換と交流を目的とした情報発信誌です．毎回，いくつかの研究関連の記事と，特定領域のスケジュール・活動報告と，各研究者の活動予定などをお送りいたします．
１．ボロノイ図とその応用国際シンポジウムを開催して − 杉原厚吉 (東京大)
２．NHC Workshop Business Meeting (兼 2004年度第３回幹事会) 議事録 − 事務局
ボロノイ図とその応用国際シンポジウムを開催して 杉原厚吉 (東京大学)
昨年9月に東大でInternational Symposium on Voronoi Diagrams in Science and Engineering (ボロノイ図とその応用国際シンポジウム) を開催した．3日間で24件の発表があり，79名の参加者を得た．そのうち海外からの参加者は18名であった．
ボロノイ図とは，いくつかの対象が，影響を及ぼす環境においてその影響の均衡を表す図形で，勢力圏図などともよばれている．影響力の与え方に多くのバリエーションがあり，それに応じてボロノイ図にも多くの変種がある．そして，その応用も多岐に渡る．このシンポジウムは，計算幾何の研究者と，応用分野の研究者がボロノイ図というキーワードを介して知見の交換をする機会を作ることを目的として開催された．
計算幾何にある程度なじんでいる人には，何でいまさらボロノイ図なのか，という疑問をもたれるかもしれない．実際，ボロノイ図は，計算幾何という学問分野が生まれた1970年代後半から1980年代前半にかけての主要なトピックの一つであり，もうずいぶん前に研究し尽くされた対象のように外からは見られがちである．
確かにアルゴリズムの理論家から見ると，ボロノイ図という畑の主要な果実はとっくに収穫され尽くされており，落穂拾いのようなドロ臭い話題しか残っていないように見えるだろう．主要な果実とは，アルゴリズム技法を華麗に駆使して，計算量を下げることのできる諸問題のことで，もう一方の落穂拾いとは，きれいな技では解決できず，ノウハウとか近似とかヒューリスティックとかいうきたない手をあれこれ尽くして何とか解らしきものが得られる問題のことである．
それにもかかわらず，この分野を取り上げて国際シンポジウムを開催したのは，応用の側から大きな要請や需要があると感じていたからである．
たとえば，有限要素法で使うメッシュを得るために，与えられた3次元領域を四面体に分割したいという要請 (これはメッシュ生成とよばれる) がある．このとき有限要素解析の精度をあげるためには，四面体がなるべくふっくらとしていることが望ましい．2次元領域を三角形に分割するときには，ボロノイ図の双対図形が，内角を小さい順に並べた列が辞書式順序で最大になるという意味の最適性をもつ．一方，3次元のボロノイ図の双対図形では，そのような最適性は保証されない．しかし，ほかによい手があるわけでもないので，ボロノイ図の双対図形から出発して，いろいろな工夫を加味しながらなんとかそこそこよいメッシュを得ようとするのが一つの有望な方向である．これなどは，理論の立場から見ると，典型的な落穂拾いの課題であろう．
一般に，アルゴリズムを作るまでの道のりより，アルゴリズムを作ってからそれが実用に使われるまでの道のりの方が長いことが多いように思う．なぜなら，アルゴリズムを実際に使えるものにするという作業は，ソフトウェアへの単なる翻訳ではないからである．アルゴリズムを構成する段階では，最も重要なところを抽出して単純化した問題を対象とするのに対して，その成果を実用に供しようとすると，理論作りでは捨象した多くの制約や事情を考慮してアルゴリズムを変更しなければならない．そらに，誤差その他の外乱に対して安定に動作するロバスト性も確保しなければならない．その手間は一般に非常に大きい．
私の今までのいくつかの経験からは，アルゴリズムを作ったところで自分の役目は終わったとみなして，使いたい人はどうぞそれを勉強してプログラムにして自由に使って下さいと言っても，現場の人は誰も使ってはくれない．現場では，次々とこなすべき仕事があって，勉強に十分な時間がとれなかったり，たくさんあるアルゴリズム理論のどこをどう学べば自分の問題が解けるのかよく分からなかったりして，なかなか手を出してはもらえない．
したがって，自分の作ったアルゴリズムを本当に使ってもらいたかったら，こんな風に使えますよと，ある程度の例が示せるところまで，ソフトウェアを実装するところも，現実的制約を加味するところも，こちら側で面倒を見なければならない．しかしそのためには，現場の事情を理解するなどこちら側も時間を割いて勉強しなければならないから，それ相当の覚悟がいる．
これらのことを考えると，アルゴリズムの研究者にとって，自分の作ったアルゴリズムが実用に使われるまでの道のりのうち，どこまでを自分自身で面倒を見るべきかは大きな問題であろう．ここから先は，それぞれの研究者の人生観，主義などに関わるものであり，それぞれが自分で選択するしかない．理論体系の構築に精力を集中する立場から，現場にどっぷり浸かって最後まで見届ける立場までの中間にいろいろな立場があり得るだろう．
話をボロノイ図のシンポジウムに戻すと，そこで現場の需要に応える実用的成果がたくさん発表されたというわけではない．しかし，こんな問題にこんな風に使えそうですよと，研究者の側から応用を指向したメッセージはたくさん出されたと思っている．そこでの応用分野は，メッシュ生成，分子の立体構造の解析，画像や立体形状のデータ圧縮，データ補間，航路計画，パッキング，消費者行動のモデリング，スポーツのチームワーク解析など多岐に渡った．
詳しい内容を知りたい方には，シンポジウム論文集の残部があるので，杉原まで郵便住所をご連絡されたい．
また，日本応用数理学会公認英文誌Japan Journal of International and Applied Mathematics (JJIAM) の第22巻2号 (2005年6月発行予定) は，このシンポジウムの特集号として編集が進んでおり，10編の論文が掲載される予定である．
なお，本シンポジウムは最初は1回限りのものとして企画したが，幸い年1回開催されるシリーズとして引き継いでいただいた．第2回目は，今年 (2005年) 10月10日から13日に韓国のソウルで開催される．また，来年の第3回は，スペイン，カナダ，アメリカ合衆国が誘地に名乗りを上げてある．
ボロノイ図という理論的には成熟した分野が，広範な応用の現場へ浸透していくのを支援する場として，このシンポジウムシリーズが役立つことを願っている．
NHC Workshop Business Meeting (兼 2004年度第３回幹事会) 議事録 事務局
日時：2005.03.02, 20:00--21:00
場所：京都ロイヤルホテル会議場（祥雲）
出席者：国際会議参加者より約４０名（特定幹事，招待講演者多数を含む）
海外からの招待講演者からの声を多く得ることを目的とし，
まず領域代表者よりプロジェクトの概要を説明し意見を求めた．
以下に主要な論点を記する．
・
結果の出し方が重要，つまり科研費の成果の出し方は？
どんな結果を出すと約束したか？
例えばこの会議が成功したと何を持って主張できるのか？など．
・
この会議の招待講演主体というのは面白い試みである．
新しいモデル，問題などの提案が多くあり，非常に有意義なものとなった．
・ この会議で得られた情報を送ってくれれば
まとめてデータベースを作っても良い（PCCより提案）．
・ 海外にも類似のプロジェクトがある．
例えばALADDIN PROJECT(http://www.aladdin.cs.cmu.edu/)は
金額も目的も似ている．ただ，ALADDINは年ごとに特定のトピックに
限定して具体的な成果を出している．
・
ヨーロッパのプロジェクトでは，１週間程度の期間，選ばれた学生を集めて，
２〜３のホットな話題に限定してスクールを行っている．
これを行えばプロジェクトも継続する．
・
日本の学生を海外の機関で２〜３ヶ月面倒みてくれるか？→OK
・
海外のプロジェクトと共同企画などは可能か？→可能
・
本プロジェクトの成果に対して一部に楽観的な見方があるが，どうか？
他の分野では（例えばORなどでも）具体的な成果をどんどん出している．
・ 教育や啓発（一般や高校生対象）も重要．
・ 雑誌や新聞などメディアの影響は大きい．
事務局まとめ：
今回の国際会議についてはたいへん好評であり，今後の継続に対する期待
もあった．一方プロジェクト全体については，どう具体的な成果を出して
いくかが中心的な問題点として議論された．その中で，短期間のスクール
による学生の教育や，学生の交流，メディアを利用した啓発活動など，興
味深い提案が得られた．また，話題を限定しての会議というのは，現在推
奨しているミニ研究集会と一致しており，力づけられた．そして本プロ
ジェクトに対して多くの海外の有力な研究者達が今後の協力を力強く約束
してくれたことは，何よりも大きな成果と言える．
★
ミニ集会，どんどん企画して下さい．楽しく活発に研究しましょう
★
今年度の報告書をまとめます，３月末までに書いて下さい
成果報告書の執筆依頼
領域としての成果報告書を作成する時期となりました．A01
から C11 の
研究課題ごとに，「研究活動報告」と「発表文献リスト」を御執筆いただき，
原稿投稿のページより御提出いただけますようお願い申し上げます．
詳細は以下を御覧ください．提出〆切は3月31日(木)
午後５時です．
http://keisan-genkai.lab2.kuis.kyoto-u.ac.jp/members/reports.html
ミニ研究集会
JAISTミニ集会
「研究の種をいかに育てるか」 (浅野哲夫,
上原隆平, 元木光雄, Arijit Bishnu)
3/12(土)
10:00-17:00 JAIST 情報科学研究科 コラボレーションルーム
日大ミニ集会 (戸田 誠之助(田中圭介グループ))
chordal graphに関連した計算問題やアルゴリズムを中心に，講演と新たな課題探求に向けたディスカッションを行う予定です．
3/19(土) 10:00-17:30 日本大学・文理学部・8号館１階レクチャーホール
列挙合宿 (宇野毅明・中野眞一)
3日間、泊り込みで列挙アルゴリズムに関する雑談をします。
3/29(火)13:00 - 31(木)11:30 群馬県伊香保町
群馬大学セミナーハウス
3/17(木) アルゴ研,
東芝科学館, 川崎
3/18(金)-19(土) コンプ研, 東工大（2日間）, 招待講演 岩間一雄 (京大)
5/19(木)-20(金) アルゴ研・コンプ研連続開催, 九州大
5/21(土)-24(火) STOC, バルチモア
6/6(月)-8(水) SoCG05, イタリア・ピサ
6/19(日)-23(木) SAT, イギリス・セントアンドリュース
6/22(火)-25(土) WG, フランス・メッツ 参加表明, 宇野
7/11(月)-15(金) ICALP, ポルトガル・リスボン
7/11(月)-15(金) IFORS, ハワイ,
8/15(月)-17(水) WADS, カナダ・ウォータールー
8/16(火)-29(金) COCOON, 中国・昆明
8/29(月)-9/2(金) MFCF, ポーランド・グダニスス
10/3(月)-6(木) ESA, スペイン・イビザ
12/19(月)-21(水) ISAAC, 中国・海南島
ニュースレター各号は電子メールで配布する予定です．短い記事や連絡事項は全て掲載しますが，長い記事，イベントの詳細などはwebページに掲載する予定です．webページには詳細まで全てを載せた完全版を掲載して，目次，あるいは各記事の末尾のURLを参照すると，web版の同じ記事を参照できるようにいたします．
記事は，各回，１つの研究課題に担当をお願いする予定です．各研究課題で2000-4000字程度，研究に関わる記事を書いていただければと思います．通常，このようなニュースレターでは，研究成果を報告するのが一般的だと思われますが，この特定領域では「研究者の交流」に焦点を当てたいため，「研究の成果以外」の記事を面白く解説していただければと思います．例えば，最近参加した国際会議の情報を，どのようなものが流行っていたか，何が面白かったか，などの主観的な解説を交えて報告したり，最近考えている問題，あるいはオープン問題を，この辺までは解けるがここがうまくいかない，といった解説を交えて紹介する，という形です．
また，研究者間の交流を促進するため，各研究者の，国内外の会議への出席予定を集約して掲載していこうと考えています．研究者の交流には，顔をあわせる回数を増やすことが肝要です．他の研究者の参加予定がわかれば，会議への出席のモチベーションを高めることにもつながり，それがディスカッションや研究成果を生むきっかけにもなるでしょう．特定領域メンバーの皆さんには，自分のわかる範囲で，国内外の会議・研究会の情報と，自分の参加予定を教えていただければと思います．
この他，個人からの寄稿を募集いたします．100-1000字程度で，情報宣伝されたいことを自由な形式で書いて送っていただければ，掲載いたします．メールで配布する関係上，テキスト形式のものしか扱えませんが，そこはご了解お願いいたします．
★ ニュースレター編集委員では，皆様からのご意見をお待ちしております．編集方針や内容の追加など編集全体にかかわることから細かいことまで，幅広いご意見をお願いいたします．
■■ 新世代の計算限界 ニュースレター ■■
編集委員長 宇野 毅明 uno@nii.jp (問合せ先)
副編集委員長 牧野 和久 makino@sflab.sys.es.osaka-u.ac.jp