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?」と間違って言ってしまい，それで更に会場が笑いに包まれた，ということがあった．本論とは全く関係ないけれども．