CCCG 2日目

今日も報告します．

The Centervertex Theorem for Wedge Depth

Gary L. Miller, Todd Phillips, Donald R. Sheehy

n点集合Pの中心点 (centerpoint) とは，それを含む任意の閉半空間がPの点をn/(d+1)個は含むような点のことである．しかし，中心点はPの点である必要がない．この研究は中心点の定義の「閉半空間」というところを「apexにおける角度が3π/2であるwedge」に置き換えると，同じ定理が成り立ち，しかも中心点をPの点から選べるということを証明している．

Streaming 1-Center with Outliers in High Dimensions

Hamid Zarrabi-Zadeh, Asish Mukhopadhyay

ストリーム計算の話で，d次元の点がどんどんとやってくるときに，外れ点をz個許した1-センター (最小包含球) を近似的に求めるという話．基本的にはZarrabi-ZadehとChanによる1-センターに対するストリーム・アルゴリズムを基にして，そこに外れ点の分を上乗せしている．

Constant-Working-Space Algorithms for Geometric Problems

Tetsuo Asano, Gunter Rote

作業領域が定数ワードしかないような場合にアルゴリズムを構築する話．ボロノイ図とドローネ三角形分割がO(n^2)時間，最小全域木がO(n^3)時間，とのこと．

Every four-colorable graph is isomorphic to a subgraph of the Visibility Graph of the Integer Lattice

David Flores-Penaloza, Francisco Javier Zaragoza Martinez

聞きにいかなかったけど，論文集を見ていて面白いと思ったからここで紹介します．
Kara, Por, Wood (2005) は2次元整数格子の可視性グラフ (これは無限グラフ) の染色数が4であることを示した．ここでは，任意の4彩色可能グラフが2次元整数格子の可視性グラフの部分グラフと同型であることを示している．実際には完全4部グラフを構成することで証明している．

Approximating Maximum Flow in Polygonal Domains using Spanners

Joondong Kim, Joseph S.B. Mitchell, Jingyu Zou

障害物のある多角形領域の中で最大流問題を考える．ただし，障害物は全部「点」であるとして，フローもある幅を持って流すものとする．これは点障害物が作るグラフのある種の最短路を求める問題に帰着され，そのグラフのspannerを構成することで高速な2近似アルゴリズムを設計している．

Bold Graph Drawings

Marc van Kreveld

実際のグラフ描画において，頂点は円板，辺は長方形として描かれるので，それを数学的にモデル化して論じた．特に，曖昧さを排除した描画がどのようなときにできるのか，また，曖昧さの規準の間の関係がどうなっているのかということを詳しく考えている．

Defining and computing accessibility radius

Vishal Verma, Jack Snoeyink

分子生物学をモチベーションにした話．大きな分子のある部分に小さな原子が入り込めるかどうかという問題を計算幾何学的に論じた．特に，ボロノイ図やpower diagramを用いて高速に計算ができるようにしている．

Intrinsic Multiscale Geometry

Leonidas J. Guibas

今日の招待講演．Point cloud dataというものは世の中にたくさんあって，物体の表面からとった3dスキャナのデータ群とか，センサネットワークにおけるセンサ群とか，機械学習におけるデータ点 (標本) の集まりとか，そういうものが例である．そういうものに対して，点自体の位置が分かっているわけではないけど，点どうしの距離は分かっているという状況で，どのような問題が考えられ，それをどのようにして解けるか，という話を講演者の最近の研究に沿って紹介されていた．という感じの話だったと思う．

How to make a picturesque maze

Yoshio Okamoto, Ryuhei Uehara

自分の「絵画的迷路生成」の話．なんか非常に受けがよかった．今までした講演の中で一番受けがよかった．いろんな人がいろんな質問をして，いろんなアイディアを出してもらったり，やっぱり皆さんこういう話題が好きなのですね．大変ありがたかったです．とても励みになりました．

An Inequality on the Edge Lengths of Triangular Meshes

Minghui Jiang

Aurenhammer, Katoh, Kojima, Ohsaki, Xu (2002) の予想を肯定的に解決．定理の内容は「多角形のtriangular meshが2つあったとき (それをA，Bとする)，Aの頂点数がBの頂点数以下のとき，Aの最大辺長はBの最近点対間距離以上である」というもの．印刷されて配布された論文の内容は間違っているということなので，注意．

Integer Point Sets Minimizing Average Pairwise \ell_1 Distance: What is the Optimal Shape of a Town?

Erik D. Demaine, Sandor, P. Fekete, Gunter Rote, Nils Schweer, Daria Schymura, Mariano Zelke

2次元グリッド上のn個の点の集合の中で，それらの2点間\ell_1距離の和が最小になるものはどんな集合でしょうか？という問題．この問題に対してO(n^{15/2})時間アルゴリズムを与えている．