1 2 1 2 河村彰星（[email protected]

平面上に多角形が幾つか与えられたとき，これをすべて囲む長さ最小の壁を見つけたい．
例えば入力が下左図のように置かれた四つの単位正方形である場合，中央と右に示された二
つの赤い壁はいずれも長さ 16 で最短である．入力の正方形四つがもっと近くに置かれてい
れば中央のように纏めて囲む解が良く，離れていれば右のように別々に囲む方が良い．
1
1
2
2
入力例（左）と二つの最適解
（中央，右）
．
未解決問題この問題をうまく解く方法を見つけよ．（または困難性を示せ．）
まずは「入力の多角形を幾つかに分ける分け方をすべて試す」よりも良い方法があるだろ
うか．入力される多角形の形を制限（例えば上の例のごとく軸に平行な単位正方形に）した場
合は如何．もし厳密な最適解が難しい場合、近似算法はあるか．
これは論文［1］の末尾問われている問題（の特殊な場合）である．
［1］ A. Kawamura, S. Moriyama, Y. Otachi, and J. Pach. A lower bound on opaque sets. In
Proc. 32nd Annual Symposium on Computational Geometry (SoCG 2016), to appear.
河村彰星（[email protected]）

Download Report