CCCG 3日目

最終日です．半日しかありませんでした．

On the Dilation of Delaunay Triangulations of Points in Convex Position

Shiliang Cui, Iyad A. Kanj, Ge Xia

連結な幾何グラフの2頂点間のdilationとはその頂点間のグラフ上の(ユークリッド重み付き)距離をその2点間のユークリッド距離で割ったものとして定義する．グラフのdilationは2頂点間のdilationの最大値とする．歴史をすっとばして，Jit Boseが2007年に挙げた未解決問題は「凸の位置にある点集合のDelaunay三角形分割のdilationは最悪いくつになるか？それはπ/2 (だいたい1.5708) か？」というものであった．この研究ではそのような場合のdilationの最悪値が2.33以下であることを示している．

The spanning ratio of the Delaunay triangulation is greater than \pi/2

Prosenjit Bose, Luc Devroye, Maarten Loffler, Jack Snoeyink, Vishal Verma

上のと同じ問題でこっちは下界の方．下界としておよそ1.5810を与えた．つまりBoseの未解決問題を否定的に解決した．凸の位置にない場合に対してもおよそ1.5846という下界を与えている．

Relaxed Gabriel Graphs

Prosenjit Bose, Jean Cardinal, Sebastien Collette, Erik D. Demaine, Belen Palop, Perouz Taslakian, Norbert Zeh

GabrielグラフとDelaunay三角形分割を補間するようなα-Gabrielグラフという概念を与えている．これはβスケルトンと密接に関わりのある概念で，β=sin(α/2)としたときのβスケルトンとDelaunay三角形分割の共通部分としても定義できる．論文では，α-Gabrielグラフのdilationとルーティングへの応用を調べている．

Teaching Computational Geometry, II

Raimund Seidel

Raimund Seidel自身が1993年にCCCGで「Teaching Computational Geometry」という講演をしてから十数年が経ったので，その間の進展と教えるべき内容，教え方について発表者の経験や意見をまとめた．特に「Invariantが重要である」という意見は私が常々思っていることで，このブログでも何度か書いている (つもりでいる) が，それを再認識した．他にはrandomizationの役割が大きくなってきて無視できないという話，学生は実装して感覚をつかんだ方がよいけどのそのためのsandboxがないから欲しいという意見，幾何学的(点-直線)双対性の教え方，データ構造は学生に嫌われるという話，摂動や数値計算をどう扱うかという話，線形計画ではMegiddo, DyerやMatousek-Sharir-Welzl，Clarksonを教えてもいいんじゃないかっていう話，など．