三村 崇晃
2014/4/16 (水), 15:00-18:00
東京大学 工学部6号館 235号室
円による被覆問題とは、ある条件を満たす円の集合から、平面上に与えられた有限個の点をすべて被覆するようにいくつかの円を選ぶ問題である。目的と円に課す条件に伴いさまざまな問題が知られており、有限個の単位円板からいくつかを選び、その個数を最小化する被覆問題、Discrete Unit Disk Cover(DUDC) problemについては計算幾何の分野においてよく研究されている[1]。
本研究では円の半径はすべて等しいが中心の位置については任意にとれるとして、被覆する円の個数を最小化する問題をとりあつかう。以上の制約のもと被覆される点を一辺1の正方形の内部から一様ランダムにとり、最適解の統計的なふるまいを数値実験により調べた。この問題はNP-hardであることが分かっており[2]、本研究では近似アルゴリズムとしてマルコフ連鎖モンテカルロ法を用いた。その際に問題がDUDCに帰着できることを示す。また、最適解の平均のふるまいを記述するために適切なスケーリング変換を提示する。
参考文献
[1] R. Acharyya, M Basappa, G. K. Das, Unit Disk Cover Problem in 2D, in: ICCSA, LNCS 7972, pp. 73-85(2013).
[2] R. J. Fowler, M. S. Paterson, L. Tanimoto, Optimal packing and covering in the plane are NP-complete, Info. Proc. Lett. 12(3), 133-137(1981).
