WADS 1日目
WADSとは「Workshop on Algoirthms and Data Structures」です．2年に1回，基本的にカナダで行われています．この会議もパラレルセッションで進んでるので，自分の聞いた話だけを抜き出して紹介します．
Algorithms meet arts, puzzles, and magic
Erik Demaine
招待講演1件目．講演者自身の経験から，芸術・パズル・マジックとアルゴリズムがどのように互いを刺激し合っていったか，ということが現在進行中の研究なども含めて紹介された．講演者が6歳のときの写真も含めた生い立ちから始め，折り紙作品，ガラス細工作品などの工芸 (の写真，および，実物)，論理手品の実演から，最新の研究成果まで盛りだくさんの内容にも関わらず，聴衆を飽きさせないのはすごい．「数学は芸術だから，数学者は芸術家」，「数学はパズル」という講演者のことばも私が常日頃考えていることで，元気になった．
Connect the Dot: Computing Feed-links with Minimum Dilation
Boris Aronov, Kevin Buchin, Maike Buchin, Marc van Kreveld, Maarten Loffler, Jun Luo, Rodrigo Silveira, Bettina Speckmann
面白い．
単純多角形Pの内部に点pがあるとき，pからPの境界のある場所へ線分を引いて，pからPの境界の点までのdilationを最小にするにはどうしたらよいか，という問題を考えて，高速なアルゴリズムを設計している．そのた，線分の数を複数にしたり，考えている単純多角形を「現実的」なものにした場合を考察したりしている．線分の数が複数の場合の難しさがよくわかっていないようなので，そこは考えてみたい．
Reconfiguration of List Edge-Colorings in a Graph
Takehiro Ito, Marcin Kaminski, Erik D. Demaine
リスト辺彩色が2つ与えられたときに，一方を他方に変換できるかどうかという問題を考察．一般の場合は (平面的グラフでリストの大きさがどの辺に対しても6であっても) PSPACE完全．木やパスの場合の考察も少し与えている．
On reconfiguration of disks in the plane and related problems
Adrian Dumitrescu, Minghui Jiang
平面上に大きさの同じ円板がn個与えられていて，それらを1つずつ平行移動させることで所望の位置へ動かしたい．何回平行移動をさせればよいでしょうか？という問題を考える．Albellanasら (2006年) によって2n-1回の移動で常に十分であり，あるときには8n/5回の移動が必要であるということが示されていたが，この論文では，5n/3-1回必要なときもあるということを示している．また，最小平行移動回数を求める問題がNP困難であることも示されている．
Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs
Chenyu Yan, Yang Xiang, Feodor Dragan
単位円グラフに対するcollective tree spannerを構成するという話．その応用としてセンサ・ネットワークにおけるルーティングも議論している．基本的なアイディアはある種のseparator theoremを単位円グラフに対して証明し，それを用いてspannerを構成することにある．
発表者が来なくて，代わりにあらかじめ用意されたビデオを上映することで発表に代える，という今までに見たことのない発表(?)だった．
New results on visibility in simple polygons
Alexander Gilbers, Rolf Klein
単純多角形に対する美術館問題で，各点から見える範囲が多角形全体の面積の1/rであるとき，εネット定理から必要な監視員の数がO(r log r)になるということをKalaiとMatousek (1997年) は証明している．このオーダー記法の定数はεネット定理から来る定数と，可視性に関する集合族のVC次元に関する定数の積である．この後者の方を深めているのがこの論文である．細かいところについては記憶なし．
A scheme for computing minimum covers within simple regions
Matthew J. Katz, Gila Morgenstern
単純多角形Pとその中にいくつか点が与えられたとき，Pに納まっている円板の集合でそれらの点をすべて被覆したい．円板の数を最小にするにはどうしたらよいか，という問題の考察．この問題を集合被覆問題だと思って定式化すると，弦グラフ (chordal graph) の最小クリーク被覆問題になり，よって多項式時間で解けますよ，というのが結果．結果自体は円板でなくてもある定められた凸集合の拡大縮小コピーを平行移動させたもので被覆する，というバージョンに拡張できる．
On the power of the semi-separated pair decomposition
Mohammad Ali Abam, Paz Carmi, Mohammad Farshi, Michiel Smid
Well-separated pair decompositionは近年の計算幾何では見逃せない概念になっているが，pairに現れる集合の要素数和が最悪の場合に大きくなってしまうという欠点がある．この論文ではVaradarajanが提案したsemi-separated pair decompositionを用いて，例えばspannerに関する既存のアルゴリズムを単純化したりしている．Semi-separated pair decompositionには上に述べたwell-separated pair decompositionの欠点がないことが重要である．
Succinct orthogonal range search structures on a grid with applications to text indexing
Prosenjit Bose, Meng He, Anil Maheshwari, Pat Morin
{1,...,n}×{1,...,n}のグリッド上の点集合に対するorthongal range search structureでsuccinctなものを提案 (これでは全然説明になってないかも...)．Makinen and Navarroの既存の結果をloglog nだけ改善している．
