SoCG 2日目
レポートします．
Decomposition of Multiple Coverings into Several Parts
Janos Pach and Geza Toth
固定した中心対称凸体のコピーを平面上に置いて各点が少なくともm個のコピーに含まれるようにする．
そのとき，コピーの族を分割して，それぞれの分割では各点がk個のコピーに含まれるようにできるか，という問題．
mの上界としてO(k^2)を与えている．
An Optimal Generalization of the Centerpoint Theorem, and its Extensions
Nabil H. Mustafa and Saurabh Ray
中心点定理は，与えられた点集合に対して，その集合の点をたくさん含む凸集合はどれもある特定の1点を含むと言っている．
この「たくさん」の度合いは2n/3点で (nは与えられた点集合の点数)，これはタイト．
ということで，「ある特定の1点」を含むという部分を「ある特定のk点のなかのどれか」に変更した一般化を考えたのがこの論文．
面白い．
There Are Not Too Many Magic Configurations
Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, and Gunter Rote
平面上に与えられたn点を考えて，各点に重みを与える．点集合が定めるアレンジメントの直線上の重み和がどれも1にできる場合，そのような点集合をmagic configurationと呼ぶ．
Murtyはmagic configurationが，(1) 一般の位置にある点集合，(2) 全てが一直線上にある点集合，(3) 1点以外全てが一直線上にある点集合，(4) failed fano configurationと呼ばれる7点の集合とその射影変換像 の5つに限られると予想した．
この論文ではその予想が正しいことを証明している．
Gallaiの定理の証明のような技法を使ってるけど，聞いてもよく分からなかった．
Quadratic and Cubic B-Splines by Generalizing Higher-Order Voronoi Diagrams
Yuanxin Liu and Jack Snoeyink
うまく三角形分割を作って，スプライン補間をしたいという話 (だと思う)．
そのためにcentroid triangulationというのを導入している．
未解決問題がたくさん．
Snap Rounding of Bezier Curves
Arno Eigenwillig, Lutz Kettner, and Nicola Wolpert
Optimal Simplification of Polygonal Chain for Rendering
Lilian Buzer
折れ線が与えられて，間引くことでその折れ線を簡単にする．
誤差規準と許容誤差を固定して，それに関して残す点の数を最小化する．
既存の2つの手法を混ぜて使うことで，よいアルゴリズムを作っている．
Streaming Algorithms for Line Simplification
Mohammad Ali Abam, Mark de Berg, Peter Hachenberger, and Alireza Zarei
上と同じ問題だけど，使う点の数を固定して，与えられた誤差規準を最小化しようとしている．
しかも折れ線がストリームとして来るモデルを考えている．
誤差規準はハウスドルフ距離とフレシェ距離．
よく分かった．楽しい．
The Theory of Multidimensional Persistence
Gunnar Carlsson and Afra Zomorodian
Persistent homologyの話．はじめの方は面白かったのに，途中で完全に気を失った．
Manifold Reconstruction in Arbitrary Dimensions using Witness Complexes
Jean-Daniel Boissonnat, Leonidas J. Guibas, and Steve Y. Oudot
曲面再構成問題で，滑らかな多様体を考えてる．
coconeとかwitness complexとか，知ってる言葉が出てきたけど，やっぱり気を失った．
Probabilistic Embeddings of Bounded Genus Graphs into Planar Graphs
Piotr Indyk and Anastasios Sidiropoulos
種数が定数のグラフを平面グラフに埋め込むとき，歪みをO(1)にできるという話．
ただし，確率的に行わないといけない．
Non-separting cycleでうまく切り開いていくという手法．
Distributed Computation of Virtual Coordinates
Mirela Ben Chen, Graig Gotsman, and Camille Wormser
貪欲ルーティングに関する話．
平面的グラフをうまく平面に埋め込んでユークリッド距離に関する貪欲ルーティングが常にうまくいくようにできるかどうかは未解決だけども，この論文では，違う距離を定義して，その距離に関しては貪欲ルーティングが常にうまくいくように埋め込めるということを示している．
A Space-Optimal Data-Stream Algorithm for Coresets in the Plane
Pankaj K. Agarwal and Hai Yu
データストリームのアルゴリズムの話で，Chanの構成にある対数因子が除去できたという結果 (だと思う)．
技法は面白い．
On Regular Vertices of the Union of Planar Convex Objects
Esther Ezra, Janos Pach and Micha Sharir
平面上のn個の凸体のアレンジメントの頂点数は最悪の場合Ω(n^2)になるけれども，ここでは「regular」なものだけを考えることにしている．
頂点がregularとは，その頂点を作る2つの凸体の境界が2点でしか交わらないことである．
Szemeredi-Trotterの定理のようなカッティングをつかった論法で，およそO(n^{4/3})という上界を証明している．
この発表はJanos Pachが行なったが，彼にとってはじめてPowerPointを使った発表だったようで，それも興味深かった．
On the Number of k-Rich Transformations
Jozsef Solymosi and Gabor Tardos
複素数の集合Aと変換Tが与えられて，AとT(A)の共通部分のサイズを考える．
そのサイズがkになるような線形変換の数を見積もる．
結果として，タイトな上界 O(n^4/k^3) を示している．
また，同じ問題でメビウス変換に対しては O(n^6/k^5) という (タイトかどうか分からない) 上界を示している．
面白い．
Similar Simplices in a d-Dimensional Point Set
Pankaj K. Agarwal, Roel Apfelbaum, George Purdy, and Micha Sharir
表題どおりの問題．
3次元空間におけるn点の中の相似三角形の数の最大値がO(n^{13/6})．
d次元空間におけるd-2次元単体，d-1次元単体に対しても結果を与えている．
