SoCG 1日目

計算幾何ばかりでいいですね．パラレルセッションでどちらにいこうかすごく迷ってしまいます．
今日聞いた話．

Guard Placement for Wireless Localization

David Eppstein, Michael T. Goorich, and Nodari Sitchinava

単純多角形の頂点に見張りを置いて，多角形の内部をうまく表現するためにどうしたらよいか考える．
面白い問題．CSG (Constructive Solid Geometry) が1つの動機となってるところも面白い．

Aperture-Angle and Hausdorff-Approximation of Convex Figures

Hee-Kap Ahn, Sang Won Bae, Otfried Cheong and Joachim Gudmundsson

平面上のコンパクトな凸体をそれに内接する凸多角形で近似する問題．
視野角とハウスドルフ距離が近似の尺度として用いられている．
それらについてFeketeとBrassの予想があったが，この論文はそれを解決している．

Traversing a Set of Points with a Minimum Number of Turns

Sergey Bereg, Prosenjit BOse, Adrian Dumitrescu, Ferran Hurtado, and Pavel Valtr

1辺の長さがnの立方格子を埋め尽くすaxis-parallelな線分だけからなるパスの中で折れ点の数が最も少ないものを見つけたい，という話．
次元が3の場合を解決し，より高次元の場合にも上界と下界を改善している．

Thick Non-Crossing Paths and Minimum-Cost Flows in Polygonal Domains

Joseph S.B. Mitchell and Valentin Polishchuk

単純多角形の頂点上に位置する複数の始点終点ペアに対して，それらを結ぶパスで太さが定められた値以上になるものを見つける問題．
話が分かりやすかった．

Finding Curvature-Constrained Paths that Avoid Polygonal Obstracles

Jonathan Backer and David Kirkpatrick

単純多角形で，内部にいくつか多角形障害物がある場合に，始点と終点が与えられてその間を結ぶパスで曲率が定められた値に収まるものを見つける問題．
これはあまり分からなかった．

Shortest Paths on Realistic Polyhedra

Yevgeny Schreiber

3次元多面体の表面のshortest path mapを計算する問題で，去年のSoCGではSchreiber and Sharirが凸多面体に対してO(n log n)のアルゴリズムを提案し，それを一般化するというのがこの論文．

Querying Approximate Shortest Paths in Anisotropic Regions

Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang

Anisotropicな環境下で，近似最短路を求める問題というのが同じ著者たちによってSODA2007で行われたけども，今回はqueryの方を考える．
始点が定められて，終点をqueryしたときに，始点と終点を結ぶ最短路の近似長を高速に答えるデータ構造を構成するという問題．

Happy Endings for Flip Graphs

David Eppstein

楽しい．
平面上の点集合の三角形分割のフリップグラフがpartial cubeになる場合の特徴づけ．
それはempty convex pentagonを含まないということ．
これによって，empty convex pentagonを含まない点集合に対して，2つの三角形分割のフリップ距離が多項式時間で計算できることが分かる．
同様な問題は凸多角形の三角形分割が結合多面体 (associahedron) を通して考えられているが，凸多角形の2つの三角形分割のフリップ距離が多項式時間で計算できるかどうかは未解決なのだそうだ．

Offline Variants of the "Lion and Man" Problem

Adrian Dumitrescu, Ichiro Suzuki, Pawel Zylinski

平面上を追いかけまわるライオンと逃げ回る人間のはなし．
楽しそうな話だったけど，よくわからなかった．

Embedding 3-Polytopes on a Small Grid

Ares Ribo Mor, Gunter Rote, and Andre Schulz

3次元凸多面体はその組合せ型を保ちながら，頂点を整数座標に置くことができる．
これはSteinitzの定理の帰結だけども，その座標の大きさの上界としてRichter-Gebertが与えたのはO(2^{18n^2}) つまり2の18nの2乗乗のオーダーだった．nは頂点数．
この論文ではTutte埋め込みを持ち上げるMaxwellの手法により，上界をO(2^{7.55n})乗に改善している．