さらなる改善

格子に基づく上界では，半径1 + 2rの円の内部の点集合の数を数えて上界を求めてい る．その半径1 + 2rの円yの上下を切り取った図5.15に示す形y^"を考える．そのときy^"

に単位円のシートを被せると単位円のシートをどのように動かしても半径rの円が1個必

ず入る．y^"の中に完全に含まれるように半径rの円をy^"上に置いたとき，半径rの円の内

部に必ず1個以上点を含むような点集合をP_U^" とすると以下の定理が成り立つ．

図5.15: 半径1 + 2rの円の上下を切り取った形y^"

定理2. 点集合P_U^" は，どのように単位円を配置してもすべての点が被覆されることは無い．

証明. まず，得られたy^"上の点集合P_U^" を単位円で覆えたと仮定する．点集合P_U^" を覆っ ている単位円集合をU^" ={a1, a2,· · ·ap}^{とおく．ただし，}ai(i= 1, . . . , p)は単位円で，P_U^"

の点を少なくとも1つ被覆しているとする．単位円集合U^"の中から，どんなa^"∈Aに対

しても|a∩y^"|≧|a^"∩y^"|を満たすaを1つ選ぶ(図5.16)．

単位円aの中心はy^"に含まれることに注意する．ここで，y^"\aに含まれており，かつ

y^"と単位円aに接する半径rの円のうちの1つを円bとする．点集合P_U^" の構成より，円b

の内部には点が必ずあるので，Uに中にはb内の点すべてを覆う円cが含まれている(図

5.17)．また，円aとぶつかってしまうため，b内の点をU内の複数の円で覆うことはでき

ない．

次に，半径rの円dを円a, cに接するように置くと(図5.18)，補題1より円dはU内の 単位円では覆うことができない(図5.19)．点集合P_U^" の構成より，d内には必ず1つ以上 の点があるので，これは矛盾である．よって，y^"上の点集合P_U^" は，どのように単位円を 配置してもすべての点が被覆されることは無い．

ここでは点集合P_U^" = PU ∩y^"として求めた．点集合PUはy^"に完全に含まれるように

半径rをy^"に置いた場合でも，必ず半径rの円の中に点を1つ以上含む．

図5.16: 形y^"と単位円a ^図 5.17: 円bを覆う単位円c

図5.18: 半径rの円dを置く 図5.19: 単位円で覆えない半径rの円d

各格子を用いて求められたPUよりP_U^" を求め，さらに改善された上界を求めた結果を 表5.2に示す．また三角格子により求められた54個の結果を図5.20に示す．

格子の種類 求められる上界

正方格子 75

改善した正方格子 73

三角格子 54

六角格子 78

表5.2: 各格子により求められた上界

図 5.20: 上界54個

第 6 _{章 まとめ}

本論文では，複数の単位円による点集合の排他的被覆問題において，どんな配置でもす べての点を必ず覆うことができる点の個数kの上界と下界の改善ができないか計算機実験 と考察を行った．

下界については，本論文で提案する手法では改善できなかった．しかし，下界改善のた め手法は，全探索を行い計算量がとても多い．よってより高速な処理が可能なように改善 すること．全く別の新しい手法を用いることで下界を改善できないかを検討することが今 後の課題として挙げられる．

上界については計算機実験により54個に改善することができた．今後は，別の手法を 用いて，上界の改善を行えないか考察していくことが課題としてあげられる．

謝辞

研究にあたり，数々のご助言を頂いた上原隆平准教授に深く感謝致します．また，学生 生活を含め様々な面でサポートして頂いた浅野哲夫教授，岡本吉央特任准教授，清見礼助 教に厚く御礼申し上げます．