Geometric spanners with applications in wireless networks

Christian Schindelhauer, Klaus Volbert and Martin Ziegler
Computational Geometry
Volume 36, Issue 3, April 2007, Pages 197-214
http://dx.doi.org/10.1016/j.comgeo.2006.02.001

ISAAC 2004の論文．盛んに研究されているspannerのはなし．

点集合Pに対するc-spannerとは，Pを頂点集合とするグラフで，任意の2点間のそのグラフ上での最短パス距離 (辺長はユークリッド) がその2点間のユークリッド距離のc倍以下となるようなものである．
幾何的な近似アルゴリズムや，幾何的ルーティングでよく出てくる．
この概念を少しゆるくしたものがweak spannerというもので，Pに対するweak c-spannerとは，Pを頂点集合とするグラフで，任意の2点間のそのグラフ上でのあるパスが一方の点を中心として半径をその2点のユークリッド距離のc倍とした球の中にあるようなもののことである．
また，電力消費を考えたようなspannerとしてpower spannerがあり，Pに対するc-power spannerとは，任意の2転換のそのグラフ上での最短パス距離 (ただし，辺長はユークリッド距離の2乗) がその2点間のユークリッド距離の2乗のc倍以下となるようなものである．

よく考えると，c-spannerは必ずweak c-spannerとなる．
また，weak c-spannerはある (cのみに依存する) 定数Cに対してC-power spannerとなる．
そのため，「c-spannerはある (cのみに依存する) 定数Cに対してC-spannerとなるか?」という問いと「c-power spannerはある (cのみに依存する) 定数Cに対してC-spannerとなるか?」という問いが興味深い．
この論文はそのどちらの問いの答えもNoであることを示している．
しかし「weak c-spannerはある (cのみに依存する) 定数Cに対してC-power spannerとなるか?」という問いの答えがYesであることもこの論文は示している．
逆に「c-power spannerはある (cのみに依存する) 定数Cに対してweak C-spannerとなるか?」という問いの答えはNoである (これも本論文の結果)．

その他，これらのspannerを一般化した概念やそれと自己相似曲線の関係，また，sparsified Yao-graphがある定数cに対してweak c-spannerとなることの証明も議論している．
盛りだくさんといった感じ．