Abstract order type extension and new results on the rectilinear crossing number

Oswin Aichholzer, and Hannes Krasser
Computational Geometry
Volume 36, Issue 1, January 2007, Pages 2-15
http://dx.doi.org/10.1016/j.comgeo.2005.07.005

SoCG2005の論文だけど，CGTAのこの号はEWCG2005の特集号．
彼らの作っている順序タイプ (order type) のデータベースによって，直線交差数 (rectilinear crossing number) の上界・下界を更新している．
データベースについては有向マトロイドの枠組を使っていて，これはFinschi and Fukuda (2002) に似ているのかも．

On the geometric dilation of closed curves, graphs, and point sets

Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grune, Rolf Klein and Gunter Rote
Computational Geometry
Volume 36, Issue 1, January 2007, Pages 16-38
http://dx.doi.org/10.1016/j.comgeo.2005.07.004


WADS2005の論文だけど，CGTAのこの号はEWCG2005の特集号．
一部 (主にボン) で流行っているgeometric dilationの話の続き．
(直線描画とは限らない) 平面的グラフの無交差埋め込みを考えて，そのグラフ上の (辺上にあってもよい) 2点間のグラフ上の最短パスと平面上の直線距離の比を考えて，その最大値を考えている埋め込みのgeometric dilationと呼ぶことにする．
平面上の任意の点集合に対して，geometric dilationが1.678の平面的グラフの無交差埋め込みで，その点集合を含むものが存在することをEbbers-Baumann, Grune, and Klein (2006, これはISAAC2003のbest paperでもある) は示した．
また，彼らは同じ論文でgeometric dilationをπ/2よりもよくできない点集合の存在も示した．
この論文では，「π/2」を「(1+10^{-11})π/2」に改善している．
離散幾何の論文でよくあることだけれども，この小さな改善にも多くのアイディアを用いている．

ちなみに，EWCG2005でAnsgarがこの研究を発表したとき，小さな改善に対する聴衆の微笑みに「Why do you laugh at it?」というべきところを「Why don't you laugh at it?」と間違って言ってしまい，それで更に会場が笑いに包まれた，ということがあった．本論とは全く関係ないけれども．

How to get close to the median shape

Sariel Har-Peled
Computational Geometry
Volume 36, Issue 1 , January 2007, Pages 39-51
http://dx.doi.org/10.1016/j.comgeo.2006.02.003

いわゆる「コアセット」(coreset) の論文．
例えば，与えられた複数の点からの距離の和を最小にするような球面を求める問題などに対する1+ε近似アルゴリズムを与えている．
コアセットに基づくアルゴリズムの一般論に従った設計なので，当然のようにアレンジメントを使っている．

Generating realistic terrains with higher-order Delaunay triangulations

Thierry de Kok, Marc van Kreveld and Maarten Loeffler
Computational Geometry
Volume 36, Issue 1 , January 2007, Pages 52-65
http://dx.doi.org/10.1016/j.comgeo.2005.09.005

ESA2005の論文だけど，これはEWCG2005の特集号．
高階デローネ三角形分割を用いて，現実的なterrainを生成するという話．
論文では，極小数を最小化する高階デローネ三角形分割を求めることがNP困難であることも示している．

The visibility-Voronoi complex and its applications

Ron Wein, Jur P. van den Berg and Dan Halperin
Computational Geometry
Volume 36, Issue 1 , January 2007, Pages 66-87
http://dx.doi.org/10.1016/j.comgeo.2005.11.007

SoCG2005の論文だけど，これはEWCG2005の特集号．
可視性グラフ(visibility graph)とボロノイ図(Voronoi diagram)を融合した「Visibility-Voronoi complex」を提案している．
アイディアはシンプルだけど，ちゃんと定義したり，性質を調べたり，アルゴリズムを設計したりするのはかなり大変に思える．

A new characterization of the normal law

S.Y. Novak
Statistics & Probability Letters
Volume 77, Issue 1 , 1 January 2007, Pages 95-98
http://dx.doi.org/10.1016/j.spl.2006.05.020

平均0，分散σ^2の正規分布に従う独立な確率変数X，Yに対して，2XY/\sqrt{X^2+Y^2}という確率変数も平均0，分散σ^2の正規分布に従うことをShepp (1964) は示した．
この論文では，ある意味でその逆を示している．
つまり，iid確率変数XとYに対して，2XY/\sqrt{X^2+Y^2}が平均0，分散σ^2の正規分布に従うとき，X(とY)も平均0，分散σ^2の正規分布に従う．

Strong computational lower bounds via parameterized complexity

Jianer Chen, Xiuzhen Huang, Iyad A. Kanj and Ge Xia
Journal of Computer and System Sciences
Volume 72, Issue 8 , December 2006, Pages 1346-1367
http://dx.doi.org/10.1016/j.jcss.2006.04.007

STOC2004論文のジャーナル版．
次のような結果を示している．

  • 与えられたグラフに大きさkの支配集合 (dominating set) があるかどうか問う問題を考える．彼らはW[1]=FPTでなければ，この問題に対するf(k)n^{o(k)}m^{O(1)}時間アルゴリズムが任意のfに対して存在しないことを示した．ただし，nはグラフの頂点数，mはグラフの辺数である．

この「任意のf」という部分はとても重要である．

  • 与えられたグラフに大きさkのクリークが存在するかどうか問う問題を考える．彼らはSNPがSUBEXPに含まれないならば，この問題を解くf(k)m^{o(k)}時間アルゴリズムが任意のfに対して存在しないことを示した．

道具として「linear fpt-reduction」という概念を新たに提案し，うまく使っている．

Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization

Jiong Guo, Jens Gramm, Falk Huffner, Rolf Niedermeier and Sebastian Wernicke
Journal of Computer and System Sciences
Volume 72, Issue 8 , December 2006, Pages 1386-1396
http://dx.doi.org/10.1016/j.jcss.2006.02.001

WADS2005の論文．
「Iterative compression」(反復圧縮) という技法を用いて固定パラメータアルゴリズムを設計する例．
反復圧縮はgraph bipartization問題に対してReed, Smith, and Vetta (2004) が開発した技法で，この名前を付けたのは確かDaniel Marxである．
このJenaのグループの論文は読みやすくてよい．

Improved bounds for the unsplittable flow problem

Petr Kolman and Christian Scheideler
Journal of Algorithms
Volume 61, Issue 1 , September 2006, Pages 20-44
http://dx.doi.org/10.1016/j.jalgor.2004.07.006

SODA2004論文のジャーナル版．ようやく出た．
Unsplittable flow problem (多品種流問題の01バージョン) に対する近似アルゴリズムの話．
特に，ある種の貪欲アルゴリズムを考えている．
この論文は私がチューリッヒに行って3ヶ月ぐらいしたときに始めたプロジェクトで渡された論文であり，なかなか内容が理解できなかったけど，そこから何とかして結果を出したという思い出がある．