SoCG 3日目
同じく単調なレポート
New Upper Bounds on the Quality of the PCA Bounding Boxes in R^2 and R^3
Darko Dimitrov, Christian Knauer, Klaus Kriegel, and Gunter Rote
与えられた点集合の最小体積bounding boxを求めるヒューリスティクスとして，主成分分析を用いる方法があるけども，それでは最小体積をうまく近似できないことを著者は以前示していた．
この論文では，与えられた点集合の凸包を考えて，その凸包に主成分分析を適用すればある程度の近似保証ができることを証明している．
Pareto Envelopes in R^3 under l_1 and l_\infty Distance Functions
Victor Chepoi and Karim Nouioua
Kuhn (1973) によると，ユークリッド空間に与えられたn点の凸包に所属するかどうかは，その点からn点までのユークリッド距離を並べたベクトルが他の点にdominateされないことで特徴づけられる．
この論文では同じ概念をl_1距離とl_\infty距離に適用している．
Computing the Volume of the Union of Cubes
Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir
3次元空間に与えられたn個の立方体の合併の体積をO(n^{4/3}log n)時間で求めるアルゴリズムを提案．
Approximating the Centroid is Hard
Luis Rademacher
凸体の重心を計算することの難しさ．
厳密計算は#P困難．近似も困難．Barany-Furediを使った論法．
On the Hardness of Minkowski Addition and Related Operations
Hans Raj Tiwary
2つのH-多面体PとQのMinkowski和ともう1個のH-多面体が等しいかどうか判定する問題がNP困難であるという結果．
A Geometric Framework for Solving Subsequence Problems in Computational Biology Efficiently
Thorsten Bernholt, Friedrich Eisenbrand, and Thomas Hofmeister
配列に蓄えられたデータに対して，与えられた目的関数に関する最適区間を求める問題はよくでてくるけども，それを2つの2次元点集合のMinkowski和の凸包といくつかの半平面の共通部分の上での最適化問題として定式化．
そのような多角形の性質を調べて，効率のよいアルゴリズムを導いている．面白い．
On the Exact Maximum Complexity of Minkowski Sums of Convex Polyhedra
Efi Fogel, Dan Halperin, and Christophe Weibel
3次元凸多面体のMinkowski和のファセット数の最大値について．
もとの多面体のファセット数がmとnの場合，その最大値が4mn-9m-9n+26であることを示している．
On Approximate Halfspace Range Counting and Relative Epsilon-Approximations
Boris Aronov, Sariel Har-Peled, and Micha Sharir
領域探索のcounting版の近似について．
いわゆるε近似を行おうとすると，データ構造は答えが0のときにただしく0と答えないといけなくなってしまう．
そこで，「relative ε近似」というものを考えて，その構成法と領域探索への応用法を与えている．
構成法は，Welzlによるlow stabbing-number spanning treeの類似を用いている．
On Approximate Range Counting and Depth
Peyman Afshani and Timothy M. Chan
こちらも領域探索のcounting版の近似．
3次元の半空間領域countingに対して，O(n)期待領域，O(log(n/k))期待問合せ時間のデータ構造を提案している．
既存のデータ構造はモンテカルロだったが，これはラスベガス．すごい．
A Data Structure for Multi-Dimensional Range Reporting
Yakov Nekrich
矩形領域探索で，座標が0〜Uの整数に限られているバージョンの話．
他のこと考えてて，あまり聞いてなかった．
Tight Bounds for Dynamic Convex Hull Queries (Again)
Erik D. Demaine and Mihai Patrascu
Word-RAMモデルやcell-probeモデルにおいて，動的凸包問題に対するアルゴリズムと下界を示している．
更新時間がpolylog(n)の場合，最適問合せ時間がΘ(log n/loglog n)となるという結果．
Kinetic kd-Trees and Longest-Side kd-Trees
Mohammad Ali Abam, Mark de Berg, and Bettina Speckmann
動く点集合に対してkd-木を拡張するという話だけど，何を言っているか全然理解できなかった．
Fully Dynamic Geometric Spanners
Liam Roditty
動的な環境下でスパナをmaintainする問題．
辺数がO(n/ε^d)の(1+ε)-スパナをmaintainするが，挿入に対する更新時間が慣らしでO(log n)，削除に対する更新時間が慣らしでO(n^{1/3} polylog(n))になるデータ構造を提案している．
削除の方の更新時間をpolylogarithmicにした結果も最近得られたようである．
Embeddings of Surfaces, Curves, and Moving Points in Euclidean Space
Pankaj K. Agarwal, Sariel Har-Peled, and Hai Yu
Johnson-Lindenstraussのようなランダム射影による次元縮小を考えるが，距離を近似的に保存するだけでなくて，角度を保存したり (Magen 2002) もできることが知られている．
この研究では，曲面がいくつか与えられたときに，曲面上の測地距離を近似的に保存するような埋め込みを発見するアルゴリズムを与えている．
どうしてこういう問題を思いつくんだろうか．面白い．
