CCCG 1日目
査読付き国際会議ではないですが，いろいろと面白い話があります．今日聞いた話をまとめます．
New Algorithms for Computing Maximum Perimeter and Maximum Area of the Convex Hull of Imprecise Inputs Based on the Parallel Line Segment Model
Wenqi Ju, Jun Luo
点の位置に不確実性がある場合の計算幾何の話．これはユトレヒトのグループが精力的に研究を始めて，最近広く知れ渡るようになってきた．(最適化のコミュニティーでロバスト最適化と呼んでいるものと枠組は同じだと思う．)
特にこの研究ではLoeffler & van Kreveldの論文で考えた問題に対する計算量を改善している．
Optimal Empty Pseudo-Triangles in a Point Set
Hee-Kap Ahn, Sang Won Bae, Iris Reinbacher
与えられた点集合の中からある意味で最適な擬三角形を見つける問題に対するアルゴリズム．ただし，考える擬三角形は内部に他の点を含まない「空」のものだけを考える．目的は面積最大化，周長最小化，最長凹鎖長最小化．面積最大化については計算量がn^6なので，それは改善したいところ．
Clarkson's Algorithm for Violator Spaces
Yves Brise, Bernd Gaertner
Violator spaceというある種の最適化問題を公理化した枠組で，いわゆるClarksonのアルゴリズムをどのように考えるのかという話で，そのような話は前にもあったんだけど，ここではそれを単純化したよ，という内容．この公理化自体は私の好みに合うので，それ自体の組合せ的性質は調べてみたい気がした．
Computational Geometry of Contour Extraction
Pedro J. Tejada, Xiaojun Qi, Minghui Jiang
輪郭抽出は画像処理の基本的なプロセスだけども，それをピクセルベースではなくて，もっと計算幾何的に行おうという話，だと思う．
Enumeration of Polyominoes for p4 Tiling
Takashi Horiyama, Masato Samejima
ポリオミノの中である種のタイリングを作るものを列挙するという話．タイリングされる様子を表したアニメーションがうけてた．
Packing 2x2 unit squares into grid polygons is NP-complete
Dania El-Khechen, Muriel Dulieu, John Iacono, Nikolaj van Omme
(穴が空いていてもよい) グリッド多角形の中に2×2の正方形を最大いくつ詰めこめられるか，という問題がNPに入ることを示す，というのがメインの結果．NP困難性は分かっていたけども，NPに入るかどうかがよくわからなかったので，それを示すことでNP完全性がいえた，ということ．ただ，穴がない場合にはNP困難性が分かっていなくて，その場合が多項式時間で解けるのかNP困難になるのかは未解決．面白い問題．
Generalizations of Interval Graphs (Connections to Constraint Satisfaction)
Pavol Hell
これはPaul Erdos Memorial Lectureとして行われた招待講演．区間グラフとList H-coloringがどう関係しているのかという話．特にdichotomyに焦点が当てられていた．最近私もdichotomyには興味を持っているので割と楽しく聞けたけど，いかんせん昼食直後だったので1/4ぐらいの部分で記憶を失ってしまっていた．
Rigid Components of Random Graphs
Louis Theran
いわゆるErdos-Renyi型のランダム・グラフで，どのようなrigid componentが出現するかという話．
Angular rigidity in 3D: combinatorial characterizations and algorithms
Audrey Lee-St. John, Ileana Streinu
CADのソフトにSolidWorksというものがあるらしくて，そこでは角度制約というものを使ってモデリングができるらしい．それを動機として角度を固定する形のrigidityについて議論し，2次元の場合のLamanの特徴づけに似た定理を証明している．
