岡本吉央先生の記事「研究室旅行」

研究室旅行
岡本 吉央
東京工業大学
[email protected]
2010 年 2 月に開催された冬の LA で LA/EATCS 発表論文賞をいただきまして，感激してお
ります．私は賞をいただいたりする器ではないと思ってますので，何だか恥ずかしいのですが，
折角なのでいただきます．私の博士論文指導教員だった Emo Welzl からもお祝いのメールが突
然来たので驚きました．
表題にある「研究室旅行」ですが，皆さんの研究室でも行っていたり，行っていなかったり，
あるいは夏の LA が研究室旅行と見なされていたり，と，研究室によって文化は様々だと思い
ます．実はこの「研究室旅行」が今回いただいた賞と深く関係しているのです．
上記のように，私の博士論文指導教員は Emo Welzl で，私は ETH チューリヒ (スイス) の
研究室出身です．当時は「Berlin-Zurich Graduate Program “Combinatorics, Geometry and
Computation”」という研究教育プログラムがベルリンの 3 大学と ETH チューリヒを中心とし
て走っていて，私はそのプログラムに 2001 年から所属しました．国際的なプログラムだったた
め，研究室の中でドイツ語が母国語の人は半分程度で，研究テーマもバラエティーに富んでい
ました．プログラム自体では，教育アシスタントをする代わりに給料がちゃんと支払われ，コ
ロキアムやセミナー，夏学校，秋学校のようなイベントが多くあり，今振り返ってみても充実
していたと思います．ちなみに，研究室メンバーというのは，教授と研究員，博士課程の学生
のみで，いわゆる修士課程や学部生は研究室メンバーではないです．
そんな研究室で，2003 年から毎年研究室旅行が行われるようになりました．スイスの若干辺
鄙なところに 3 日から 5 日ぐらい行きます．スイスなので山間に行くことになります．その内
容ですが，ひたすら研究です．しかし，研究テーマがばらばらなので，集まって研究しようと
思ってもなかなか難しいわけです．そのため，何を行っているかというと，
「未解決問題ワーク
ショップ」です．形式は以下の通り．まず，参加者は事前にこのワークショップで解きたい未解
決問題を提出します．そして，合宿の場で問題集が手渡されます．合宿中は事前に割り当てら
れたグループに分かれて，ひたすら問題を解きます．1 日に 1 回，グループごとにどういう発見
があったかを報告します．これを何日か繰り返します．こういう形式のものです．ただ，研究
自体がメインなのではなくて，そのために卒業生や長期訪問研究員が集まって，1 年に 1 回は顔
を合わせる，ということが本来の目的です．5 日ぐらいの合宿のときには，真ん中の日にハイ
キングをします．ハイキングといっても，割とちゃんとした山登りなので，なかなか大変です．
研究に戻ると，このワークショップで重要なことは，どのような問題を提出するか，という
ことです．以下の 3 つが一般的な注意事項です．
1. 様々な研究テーマを持っている人が集まるので，誰にでも理解できる問題であること．
2. 合宿の期間は限られているので，長い間未解決であった問題や，難しい問題は避けること．
3. 問題が自分の専門に属している必要はないこと．
1
図 1: 第 1 回の合宿 (2003 年) より
この 3 つを基準にして問題が集められます．例年，30 問ぐらい集まるのですが，実際に合宿中
に人々が取り組む問題はその中の半分ぐらいです．残りの半分は参加者の嗜好に合わないか，
難しすぎると感じられるか，またはその他の理由により，話題にのぼることがありません．そ
して，実際に解かれる問題は 5 問ぐらいです．なかなか厳しいものです．
もう 1 つ重要なことがあります．それは，問題を説明するためにプレゼンテーションをしな
いことです．情報は問題集だけです．不明な点については個別に質問したりします．問題は全
部で 30 ぐらいあるのです．プレゼンテーションをして説明をしていたら，それだけで 1 日過ぎ
てしまいます．無駄な投資です．
そのような厳しい状況の中でも問題が解けるということは，そこから論文ができるというこ
とです．今回受賞した論文もその中から生まれたものです．割とそのようにして生まれた論文
があるので，私の目につく範囲で紹介します．
• M. Hoffmann, J. Matoušek, Y. Okamoto, P. Zumstein, Minimum and Maximum Against k
Lies, Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT),
Lecture Notes in Computer Science (2010), 139-149.
今回の受賞論文です．国際会議版は SWAT に出てます．高々k 回嘘をつく比較を用いて，
要素数 n の集合から最大値と最小値を見つけるために何回比較を用いればよいか，とい
う問題に対して，Aigner の上界を改善．2009 年の合宿の結果．
• M. Hoffmann, J. Matoušek, Y. Okamoto, P. Zumstein, The t-pebbling number is eventually linear in t. Submitted.
投稿中の論文ですが，5 月の COMP 研で私が発表しました．グラフ上にばらまかれた石
を t 個ターゲットに運ぼうと思うとき，最低いくつ石がないといけないか，という数が t
に関して線形であることを示した．2009 年の合宿の結果．
• K. Buchin, R. Fulek, M. Kiyomi, Y. Okamoto, S.-i. Tanigawa, and Cs. D. Toth, A tight
lower bound for convexly independent subsets of the Minkowski sums of planar point sets.
2
JCCGG 2009.
Eisenbrand らの考えた問題で，平面上の 2 つの点集合の Minkowski 和における凸独立集
合の最大サイズが何であるのか，という量の下界を改善．2009 年の合宿の結果．(この年
の私は何かたくさん解いてる気がします．)
• T. Christ, D. Pálvölgyi, M. Stojaković, Consistent digital line segments, Symposium of
Computational Geometry (SoCG) (2010), 11-18.
全，Korman，Nöllenburg，徳山の考えたデジタル半直線をデジタル線分に拡張して，彼
らの未解決問題を解決．2009 年の合宿の結果．
• K. Buchin, J. Matoušek, R. Moser, D. Pálvölgyi, Vectors in a Box (2010), Submitted.
arXiv:0912.0424.
整数計画問題に対する Dash らのアルゴリズムが擬多項式時間で動くかどうかを定めるパ
ラメータに対する上界と下界を与えた．2009 年の合宿の結果．
• T. Christ, M. Hoffmann, Y. Okamoto, T. Uno, Improved Bounds for Wireless Localization, Algorithmica 57:3 (2010), 499-516.
ワイヤレス・ネットワークにおける位置同定を動機として Eppstein らが考えた新しい美術
館監視問題に対する上界と下界を改善した．2007 年の合宿の結果．国際会議版は SWAT
’08．
• N. Alon, R. Berke, K. Buchin, M. Buchin, P. Csorba, S. Shannigrahi, B. Speckmann, P.
Zumstein, Polychromatic Coloring of Plane Graphs, Discrete and Computational Geometry 42:3 (2009), 421-442.
平面グラフの頂点に k 色を割り当てるとき (ただし，1 辺の両端点に同じ色が割り当てら
れてもよい)，どの面にも k 色すべて現れるようにしたい状況を考える．それが可能な最
大の k に対する Hoffmann と Kriegel の未解決問題を解決．2007 年の合宿の結果．国際会
議版は SoCG ’08．
• J. Matoušek, Blocking visibility for points in general position, Discrete and Computational
Geometry, 42:2 (2009), 19-22.
平面上に n 個の点があるとき，それらを結んでできる線分をすべて横断するような点集
合のサイズに対する上界と下界の考察．2007 年の合宿の結果．
• J. Matoušek, LC reductions yield isomorphic simplicial complexes, Contributions to Discrete Mathematics (electronic) 3,2 (2008), 37-39.
Civan と Yalçin が定義した LC reduction という単体的複体に対する操作に対して，1 つの
単体的複体から LC reduction によって 2 つの異なる単体的複体が得られたとしても，そ
れらが同型になることを示した．2007 年の合宿の結果．
• V. Anuradha, C. Jain, J. Snoeyink, T. Szabó, How long can a graph be kept planar?
Electronic Journal of Combinatorics, 15(1) (2008), N14.
3
図 2: 第 2 回の合宿 (2004 年) より．この年は食事も自分たちで準備することになっていたので，
大変でした．大変だったので，次の年からは食事を自分たちで準備することはなくなりました．
完全グラフの辺を 2 人のプレイヤーが順に選択していき，後手が非平面的グラフを作って
しまうまでの手数を解析し，Hefetz らの下界を改善．2007 年の合宿の結果．
• S. Smorodinsky, M. Sulovský, U. Wagner, On Center Regions and Balls Containing Many
Points, Proc. 14th Annual International Computing and Combinatorics Conference (COCOON) (2008), LNCS 5092, 363-373.
d 次元ユークリッド空間にある任意の n 点の中から (d + 3)/2 個の点を選んで，それら
をすべて含む球がもとの n 点のおよそ 4n/5ed3 個を含むということを示した．もともと
Neumann-Lara と Urrutia が考えた問題で，この結果は Bárány の下界を大幅に改善．2007
年の合宿の結果．
• K. Buchin, A. Razen, T. Uno, U. Wagner, Transforming Spanning Trees: A Lower Bound,
Computational Geometry - Theory and Applications 42:8 (2009), 724-730.
平面上の n 点集合に対する全域木を考える．2 つの全域木が隣接していることをその 2 つ
の辺が交差しないこと，として全域木全体の上でグラフが定義できる．このグラフの直
径が Ω(log n/ log log n) になりうることを示した．Aichholzer らによる下界は定数だった
ので，大幅に改善．2006 年の合宿の結果．
• J. Giesen, E. Schuberth, M. Stojaković, Approximate sorting, Proc. 7th Latin American
Theoretical Informatics Symposium (LATIN), Lecture Notes in Computer Science 3887
(2006) 524-531.
整列済みの状態からの Spearman footrule 距離が n2 /α になるまでに，行わなくてはなら
ない比較の回数が (乱択の場合でも) nα だけは必要であるという下界を示した．2005 年
の合宿の結果．
• U. Adamy, M. Hoffmann, J. Solymosi, M. Stojaković, Coloring octrees, Theoretical Com-
4
図 3: 第 7 回の合宿 (2009 年) より．夜にトリビアル・パスートをやっています．私は (ドイツ
語で) 問題を読む係．
puter Science 363 (2006) 11-17.
八分木で得られる立方体の分割において，隣接する小立方体どうしが異なる色を持つよう
に彩色するとき，必要な色の数を考察．2003 年の合宿の結果．国際会議版は COCOON
’04．
• U. Adamy, Th. Erlebach, D. Mitsche, I. Schurr, B. Speckmann, E. Welzl, Off-line admission control for advance reservations in star networks, Proc. 2nd Workshop on Approximation and Online Algorithms (WAOA ’04), Lecture Notes in Computer Science 3351
(2005) 211-224.
スター状のネットワークにおいて，葉の間に接続要求が事前にいくつか与えられる．この
とき，要求を満たしながら利益を最大にするように接続する問題を考える．この問題が
NP 困難であることは知られていたが，ここでは定数近似アルゴリズムと APX 困難性を
示している．2003 年の合宿の結果．
ちなみに，何度も出てくる「T. Uno」は宇野毅明さんです．宇野さんは研究室の長期訪問者だっ
たので，合宿に招待されています．
ここで紹介したもの以外にも小さな結果があって，それらは個別に論文として出版されてい
なくても，他の論文の中にちょっと登場していたり，謝辞に載っていたりするものがあります．
私が謝辞に登場したもの (として私が覚えているもの) は以下の 2 つです．
• P. K. Agarwal, M. Sharir, E. Welzl, Algorithms for center and Tverberg points, ACM
Transactions on Algorithms 5 (2008) No. 5.
私が関係してるところだけ述べると，平面上に赤点 n 個，青点 n 個，緑点 n 個が一般の
5
図 4: 第 1 回の合宿 (2003 年) より
位置にあるとき，赤青緑三角形を n 個上手に作ると，それらの共通部分が非空になるこ
とが知られている．そのような共通部分として現れる領域が凸にならない場合があると
いう例を構成して，謝辞に登場した．2003 年の合宿の結果．
• R. Berke, T. Szabó, Relaxed two-coloring of cubic graphs, Journal of Combinatorial Theory, Series B 97 (2007) 652-668.
無向グラフの頂点に 2 色を割り当てる (ただし，隣接する頂点に同じ色が割り当てられて
もよい) とき，一方の色が独立集合を誘導するようにする．このとき，もう一方の色が誘
導する部分グラフの連結成分がどれも小さくなるようにしたい．3 正則グラフに対して，
その連結成分の大きさに対する 6 という下界を示して，謝辞に登場した．論文の主結果は
750 という上界．2004 年の合宿の結果．
さて，この研究室合宿は今年 (2010 年) も行われて，つい先週 (6 月 30 日∼7 月 2 日) にチュー
リヒから電車とバスを乗り継いで 1 時間半ぐらいのところに行ってきました．8 回目になりま
すが，1 時間半という時間はいままでの伝統に比べて近い方です．私としてはもっと遠い方が
好みなのですが．過去にはスイスのロマンシュ語圏で行ったりしたこともありました．しかし，
毎年全部出席しているのはボスの Emo Welzl と私の 2 人だけなのです．こうなると，何が何で
もずっと出席し続けようという気になります．
こんな感じなので，私の企画するイベントは山奥で行うことが通例化しているのかもしれま
せん．しかし，都会の喧騒から離れた辺境で，昼間は研究をして，夜はビールやワインを飲み
ながら会話をしたりするのは，とても充実して楽しいわけです．こういう活動から今回の受賞
論文も生まれたのです．自分が楽しいと思うことをして，賞がいただけるのですから，ありが
たいことです．
6