複数の単位円による点集合の排他的被覆

全文

(1)Vol.2011-AL-134 No.19 2011/3/7. 情報処理学会研究報告 IPSJ SIG Technical Report. 複数の単位円による点集合の排他的被覆岡山. 陽. 介†1. 清. 見. 礼†1. 上原. 隆. 平†1 図 1 点集合とそれを覆う単位円集合 Fig. 1 A point set and unit disks covering the point set.. 電波による通信を用いたサービスでは、基地局の通信の範囲は円となる．複数の基地局からの通信が重なることで不具合がでる場合もあり，どのように基地局を配置するかが問題になる．ここでサービスの利用者を点，電波の届く範囲を単位円としたときに，重なりの無い単位円集合ですべての点を覆えるか，という問題が考えられる．本研究では，これを複数の単位円による点集合の排他的被覆問題として取り扱う．どのように配置しても必ず適当に配置した単位円の集合で排他的に被覆できる点の個数 k は 1 以上で上限があり，既知の結果として 10 5 k < 108 が知られている．本研究では，この上界を改善することを目的とし，提案手法により 10 5 k < 54 と改善することができた．. 図 2 単位円集合で覆えない点集合 Fig. 2 A point set which cannot be covered with unit disks.. 1. はじめに近年，電波を利用して提供するサービスは増加している．無線 LAN や携帯電話，テレビの電波など，多岐にわたる．電波の到達範囲は地上の円で表すことができる．電波の到達範囲を表す円が重なると，テレビの映像にゴーストが出る，無線通信が混信する，などの. Exclusive covering of point set by unit disks. 不具合が引き起こされる場合もあり，基地局をどのように配置するかが問題となる．また，サービスの利用者はすべて電波に覆われている必要があり，円が重ならないことと相反する. YOSUKE OKAYAMA,†1 MASASHI KIYOMI†1 and RYUHEI UEHARA†1. 場合もある．ここで、サービスの利用者を点，電波の届く範囲を単位円とすると，重なりの無い単位円集合ですべての点を覆えるか，という問題が考えられる．本研究では，これを複数の単位円. In services using the electric wave communication, the range of the electric wave from a base station becomes a circle. The situation where two ranges of the wave intersect can be problematic. Therefore, base station layout becomes a problem. Consider 2 points in the plane. Clearly we can cover them by disjoint unit disks. It is known that any 10 points can be covered by some disjoint unit disks, and carefully arranged 108 points cannot be covered by any arrangement of unit disks. We improve the upper bound from 108 to 54, i.e. we show an arrangement of 54 points which cannot be covered by any arrangement of unit disks.. による点集合の排他的被覆問題として取り扱う．この問題は，稲葉1) により考えられたもので，点集合の配置が与えられたとき，重なりの無い単位円集合ですべて覆えるかどうかを考える (図 1)．ここで，単位円集合により覆われる点の個数を考える．点が 1 つの場合，単位円が 1 つあればその点を必ず覆うことができる．点が 2 つの場合でも，単位円が 1 つまたは 2 つあればその 2 つの点を必ず覆うことができる．しかし，数多くの点を細かく格子状に並べると単位円で排他的に覆えないことがある (図 2)．よって，どのように配置しても必ず単位円で覆える点の個数 k は 2 以上で上限があることが分かる．既存の結果として 10 5 k < 108 が知られている1)2) ．また Peter Winkler により，60 個という上界を与える点の配置が発見されている3) ．また，Veit Elser により，55 個という上界の証明がなされた4) ．そこで本研究では，この k の. †1 北陸先端科学技術大学院大学 Japan Advanced Institute of Science and Technology. 値をより正確に評価することを目的とする．つまり k の値のよりよい上界および下界を求. 1. c 2011 Information Processing Society of Japan.

(2) Vol.2011-AL-134 No.19 2011/3/7. 情報処理学会研究報告 IPSJ SIG Technical Report. めることを目的とする．上原・浅野により示された上界は，正方格子の格子点上に配置した点集合を元に，単位円集合で覆うことができない点の配置を実現する点の個数を求めることで示されている．また稲葉により示された下界は，単位円を最も稠密に並べたときにできる隙間と単位円の面積との比をもとにして示されている．. (0,0). 本研究では 4 通りの方法で上界の改善を試みる．1 つ目は，上原・浅野の用いた正方格子の格子の幅をより大きなものにしても単位円で被覆できない点が存在することを示し，それによって改善される上界を求める．また，平面を合同な図形で隙間無く覆うことのできる正多角形には，正方形の他に正三角形，正六角形がある．ここから 2 つ目の方法として，三角格子を用いた場合，3 つ目の方法として，六角格子を用いた場合に導出される上界を求め図 3 単位円のシート S(0, 0) Fig. 3 Sheet of unit disks.. る．さらに 4 つ目に，格子を利用しない方法として，最大空円の手法を用いて上界を改善することができないか考察と計算機実験を行う．. 2. 用語の定義. 単位円のシート S(0, 0) を図 3 に示す．図 3 は実際には単位円が無限に続いている．. ここでは，本論文で用いる用語について定義を行う．. 3. 上. 2.1 円. 上原・浅野により，108 個の上界が示されている2) ．2) では，単位円のシート S(x, y) で，. 中心座標が (x0 , y0 ) かつ半径 r の円 C(x0 , y0 , r) を以下のように表す．. C(x0 , y0 , r) = {(x, y)|(x − x0 ) + (y − y0 ) 5 r )} 2. 2. 界. 2. すべての点を覆うことができない配置を実現する点の数を求めている．単位円の並べ方に. 特に r = 1 の円を単位円と呼び，C(x, y) と表す．. は，他の配置も考えられるが，まず単位円のシートの場合について考える．また，単位円の. 2.2 単位円のシート. シートの動かし方は，平行移動のみを考える．以下にその概要を示す．. 中心が (x, y) となる単位円を 1 つの構成要素とし，単位円を隙間が最も小さくなるよう. まず，単位円のシートの隙間 S(x, y) に包含される円の中で，半径が最大となる円の半径. に無限に敷き詰めたものを単位円のシート S(x, y) と呼ぶ．正確には，S(x, y) は以下で定義される．. ∞ ∪. S1 (x, y) = S2 (x, y) =. での長さは垂直二等分線の. C(2i + x, y). i=−∞ ∞. ∪. を求める．この円の中心は，単位円の中心を線分でつないだ正三角形の重心である (図 4)． √ この正三角形の高さは正三角形の垂直二等分線なので 3 となる．また正三角形から重心ま. ∪. S1 (x, 2 3i + y). S4 (x, y) =. ∪. √ 2 3 3. − 1 ≈ 0.1547 となる．次に，S(x, y) の. 隙間 S(x, y) に半径 r の円をできるかぎり詰め込むことを考える (図 5)．このときの半径 r の円の集合を R(x, y) と表すと，∀x0 , ∀y0 C(0, 0, 1 + 2r) ∩ R(x0 , y0 ) の中には半径 r の円. C((2i + 1) + x, y). i=−∞ ∞. である．正三角形の頂点から重心までの長さから単位円の半. 径をひくと，求める円の半径 r が定まり，r =. √. i=−∞ ∞. S3 (x, y) =. 2 3. が含まれる．. √ S3 (x, 2 3i + y). 次に，この半径 r の円の円周上に等間隔に点を 4 点置き，できた正方形のサイズで正方. i=−∞. 格子を作り，格子点上に点を配置する．すると半径 r の円を格子上のどこに置いても半径 r. としたとき S(x, y) = S2 (x, y) ∪ S4 (x, y)．. の円は必ず格子点を含む．つまり，単位円のシートをこの格子上に置くと，その隙間には必. 2. c 2011 Information Processing Society of Japan.

(3) Vol.2011-AL-134 No.19 2011/3/7. 情報処理学会研究報告 IPSJ SIG Technical Report. Unit disk. Equilateral triangle Circle of radius r. 図 6 108 個の上界の点の配置 Fig. 6 The arrangement of 108 points which cannot be coverd by unit disks.. 図 4 半径 r の円を求め，円周上に等間隔に点を置く Fig. 4 Points on the circumference at equal intervals for the circle of radius r.. 図 7 補題 1. Fig. 7 Lemma1.. ず格子点が含まれる．よって単位円のシートで覆ったとき，隙間に必ず点が含まれる点集合が求められた．最初に平行移動のみ考えたが，回転移動を行っても C(0, 0, 1 + 2r) の中に半径 r の円は含まれるので，結果は同じになる．C(0, 0, 1 + 2r) の内部には必ず 1 個は半径 circle of radius r. r の円が含まれるので，C(0, 0, 1 + 2r) の内部にある点の数を数えることで 108 個という上. circle of radius 1+2r. 界が得られる．S(0, 0.1543) と C(0, 0, 1 + 2r) を使い得られた点の配置を図 6 に示す．以上の方法で単位円のシートで覆えない点の配置が求められた．求められた点集合を PU とすると，求めた点集合 PU はどのように単位円を配置しても覆えないことが以下の理由で証明できる．補題 1. 互いに重なっていない単位円 C1 , C2 , C3 があるとき，C1 , C2 , C3 の中心を線分でつないだ三角形の内部には，C1 , C2 , C3 と重ならない半径 r の円を必ず 1 個以上配置できる (図 7)．定理 1. 点集合 PU は，どのように単位円を配置してもすべての点が被覆されることは無い．証明. まず，得られた半径 1 + 2r の円 y 上の点集合 PU を単位円で覆えたと仮定する．点. 図 5 単位円のシート S(x, y) に半径 r の円を詰め込む Fig. 5 Circles of radius r packed in the sheet of unit disks.. 集合 PU を覆っている単位円集合を U = {a1 , a2 , · · · ap } とおく．ただし，ai (i = 1, . . . , p) は単位円で，PU の点を少なくとも 1 つ被覆しているとする．単位円集合 U の中から，どんな単位円 a0 ∈ U に対しても |a ∩ y| = |a0 ∩ y| を満たす単位円 a を選ぶ (図 8)．. 3. c 2011 Information Processing Society of Japan.

(4) Vol.2011-AL-134 No.19 2011/3/7. 情報処理学会研究報告 IPSJ SIG Technical Report. 図 8 半径 1 + 2r の円 y と単位円 a Fig. 8 A circle of radius 1 + 2r and unit disk a.. 図 9 円 b を覆う単位円 c Fig. 9 The unit disk c covering b. 図 11 単位円で覆えない半径 r の円 d Fig. 11 The circle d of radius r that cannot be covered by unit disks.. 図 10 半径 r の円 d を置く Fig. 10 Put the circle d of radius r.. 単位円 a の中心は円 y に含まれることに注意する．ここで，y \ a に含まれており，かつ円 y と単位円 a に接する半径 r の円のうちの 1 つを円 b とする．円 b の内部には点が必ずあるので，U の中には b 内の点すべてを覆う円 c が含まれている (図 9)．また，円 a とぶつかってしまうため，b の点を U 内の複数の単位円で覆うことはできない．次に，半径 r の円 d を円 a, c に接するように置くと (図 10)，補題 1 より円 d は U 内の単位円では覆うことができない (図 11)．点集合 PU の構成より，d 内には必ず 1 つ以上の点があるので，これは矛盾である．よって，点集合 PU は，どのように単位円を配置してもすべての点が覆われることは無い．. 4. 上界の改善既存の手法では正方格子を用いて上界を求めているが，同じく平面を覆い尽くすことのできる三角格子，六角格子に変えた場合の上界も求めた．さらに，正方格子については，格子のサイズを大きくすることにより改善が行えないか検証した．また，格子に基づかない点集合をつくり，単一の格子では到達できない上界を求めることができるのではないか考察を. 図 12 周囲に内接しない正方形 Fig. 12 A square which is not inscribed to the surrounding unit disks.. 行った．. 4.1 格子に基づく改善. 図 13 大きくできる正方形 Fig. 13 A square which can be enlarged.. 4.1.1 正方格子の改善 2) で正方格子で上界を求めることができたのは，どのように単位円のシートを動かして. 4. c 2011 Information Processing Society of Japan.

(5) Vol.2011-AL-134 No.19 2011/3/7. 情報処理学会研究報告 IPSJ SIG Technical Report. 図 14 改善された正方格子により示された 102 個の点の配置 Fig. 14 The arrangement of 102 points based on enlarged square which cannot be covered by unit disks.. 図 15 三角格子の求め方 Fig. 15 Calculating the triangular lattice.. 図 16 三角格子により求められた 82 個の点の配置 Fig. 16 The arrangement of 82 points based on triangle lattice which cannot be covered by unit disks.. も，隙間の中に必ずこの正方格子の格子点が 1 点以上入るからである．ここで，三角格子や. 4.1.3 六角格子. 六角格子は，すべての頂点が周囲の単位円に同時に内接する場合があるが，正方格子を作成. 単位円のシートの隙間にできる半径 r の円の半径を広げた円 C を考えると，周囲の単位. した正方形は，どのように回転させてもすべての頂点が同時に周囲の単位円に接することは. 円と交差する点が 6 点できる (図 17)．この 6 点の距離がすべて等距離になるような円を求. ないことが分かる (図 12)．すべての頂点が同時に周囲の単位円に接していなければ，回転. めると半径が. させても必ず 1 つの頂点は隙間の中にある．. ができる．半径 r の円は，必ず半径 1 + 2r の円の中に 1 つ以上含まれる．正六角形を構成. √ 3− 6 3. = rs の円となる．できた 6 点を直線でつなぐと 1 辺が rs の正六角形. つまり，正方形を回転させ，すべての頂点が周囲の単位円に同時に内接するまでなら，正. する 6 点は，単位円のシートをどのように動かしても単位円のシートの隙間に必ず含まれ. 方形を大きくすることができる (図 13)．正方形の中心をずらして考えると複雑になるため，. る．よって，この正六角形で六角格子を作り格子点上に点を置くと，どのように単位円の. 中心軸を固定し少しずつ角度を変え，すべての頂点が周囲の単位円に同時に内接するまで. シートを動かしても必ず 1 つ以上の点が単位円のシートの隙間に含まれる．よってこの六. の範囲で正方形を大きくしていき，それらの内接する正方形の中で最も小さいものを求め. 角格子を基に上界を求めると，119 個という結果が得られた．. た．結果は一辺が 0.2278 の正方形に拡大することができた．上原・浅野が用いた正方格子. 以上のように，正方格子・改善された正方格子・三角格子・六角格子を基に求められた上. の一辺は 0.2188 だったので，正方形のサイズを約 4.1% 大きくすることができた．この正. 界を表 1 に示す．. 方形で正方格子を作り上界を求めると 102 個となり，正方格子を基にした上界が改善され. 4.2 格子に基づかない上界. た．図 14 に改善された点の配置を示す．. ここでは，格子に基づかない手法により上界を求める．まず最初に空円を定義する. 本手. √. 4.1.2 三角格子. 法での与えられた点集合 Q に対する空円とは，1 + r の円の内部に中心を持ち，内部に Q. 正方格子を作成した半径 r の円で，均等に 3 点を取りそれぞれを線分でつなぐと一辺が. の点を含まず，点集合 Q 中の 3 点で決定される円もしくは Q 内の 2 点と半径 1 + 2r の円. 3r の正三角形ができる．これをもとに三角格子を作成した (図 15)．これを基にして，82. の円周上のある 1 点で決定される円である．. 個という上界が得られた．図 16 に点の配置を示す．. 格子に基づく上界を求める際に用いた半径 r の円と半径 1 + 2r の円を利用する．半径. 1 + 2r の円の中に a 個の点からなる点集合 Q があったとする．そのとき Q が半径 r 以上. 5. c 2011 Information Processing Society of Japan.

(6) Vol.2011-AL-134 No.19 2011/3/7. 情報処理学会研究報告 IPSJ SIG Technical Report. 図 17 六角格子 Fig. 17 The hexagonal lattice.. 図 18 六角格子により求められた 119 個の点の配置 Fig. 18 The arrangement of 119 points based on hexagonal lattice which cannot be covered by unit disks.. の空円を持たなかったとする (図 19)．すると半径 1 + 2r の円の中に，全体が完全に含まれ. 図 19 半径 r の円より大きな円が入る隙間が無い点集合を持った半径 1 + 2r の円 Fig. 19 The disk of radius 1 + 2r with the point set such that any disk of radius r must contain at least one point.. るように半径 r の円を置くと，どのように置いても半径 r の円は必ず Q の点を 1 個以上含む．すなわち単位円のシートで覆うことができない点の配置が求められたことになる．そこで，ある a 個の点からなる点集合 Q に対する最大の空円の半径を求め，r より大きい場合は，その空円を構成する点を動かし半径を小さくする．これを繰り返すことで，点集合 Q 上の最大の空円の半径が r 以下となる配置を作ることができるかどうかを求める．最. 1.5 "SUCSSES_ANS79.dat". 大の空円の半径が r 以下となる配置を作ることができたら，Q より点の数を 1 つずつ減ら 1. していく．最終的に，どれだけ少ない点数の点集合でそのような配置を作ることができるかを，計算機実験により確認する．. 0.5. この手法を用いた結果，上界を 79 個に改善することができた．図 20 に結果を示す．図. 20 の周囲の円は半径 1 + 2r の円を表している．. 0. -0.5. -1. 表 1 各格子により求められた上界 Table 1 The arrangement of points which cannot be covered by unit disks from each lattice 格子の種類正方格子改善した正方格子三角格子六角格子. -1.5 -1.5. 求められる上界. -1. -0.5. 0. 0.5. 1. 1.5. 図 20 上界 79 個 Fig. 20 The arrangement of 79 points which cannot be covered by unit disks.. 108 102 82 119. 6. c 2011 Information Processing Society of Japan.

(7) Vol.2011-AL-134 No.19 2011/3/7. 情報処理学会研究報告 IPSJ SIG Technical Report. 図 22 形 y 0 と単位円 a Fig. 22 The shape y 0 and a unit disk a.. 図 23 円 b を覆う単位円 c Fig. 23 A unit disk c covering the disk b.. 図 21 半径 1 + 2r の円の上下を切り取った形 y 0 Fig. 21 The shape y 0 obtained by cutting oﬀ the top and the bottom of the disk of radius 1 + 2r.. 4.3 さらなる改善格子に基づく上界では，半径 1 + 2r の円の内部の点集合の数を数えて上界を求めている．実際には半径 1 + 2r の円 y の上下を切り取った図 21 に示す形 y 0 を考えれば十分である．. y 0 の中に完全に含まれるように半径 r の円を y 0 上に置いたとき，半径 r の円の内部に必ず 1 個以上点を含むような点集合を PU0 とすると以下の定理が成り立つ．定理 2. 点集合 PU0 は，どのように単位円を配置してもすべての点が被覆されることは無い．証明. まず，得られた y 0 上の点集合 PU0 を単位円で覆えたと仮定する．点集合 PU0 を覆って. 図 24 単位円 a と単位円 c で覆えない半径 r の円 d 図 25 単位円で覆えない半径 r の円 d Fig. 24 The disk d of radius r which cannot be Fig. 25 The disk d of radius r which cannot be covered by the unit disks a and unit disk covered by the unit disks. c.. いる単位円集合を U 0 = {a1 , a2 , · · · ap } とおく．ただし，ai (i = 1, . . . , p) は単位円で，PU0 の点を少なくとも 1 つ被覆しているとする．単位円集合 U 0 の中から，どんな a0 ∈ A に対しても |a ∩ y 0 | = |a0 ∩ y 0 | を満たす a を 1 つ選ぶ (図 22)．単位円 a の中心は y 0 に含まれることに注意する．ここで，y 0 \ a に含まれており，かつ y 0 と単位円 a に接する半径 r の円のうちの 1 つを円 b とする．点集合 PU0 の構成より，円 b の. 点があるので，これは矛盾である．よって，y 0 上の点集合 PU0 は，どのように単位円を配置. 内部には点が必ずあるので，U に中には b 内の点すべてを覆う円 c が含まれている (図 23)．. してもすべての点が被覆されることは無い．. また，円 a とぶつかってしまうため，b 内の点を U 内の複数の円で覆うことはできない．ここでは点集合 PU0 = PU ∩ y 0 として求めた．点集合 PU は y 0 に完全に含まれるように. 次に，半径 r の円 d を円 a, c に接するように置くと (図 24)，補題 1 より円 d は U 内の単位円では覆うことができない (図 25)．点集合. PU0. 半径 r を y 0 に置いた場合でも，必ず半径 r の円の中に点を 1 つ以上含む．. の構成より，d 内には必ず 1 つ以上の. 7. c 2011 Information Processing Society of Japan.

(8) Vol.2011-AL-134 No.19 2011/3/7. 情報処理学会研究報告 IPSJ SIG Technical Report. 図 26 上界 54 個 Fig. 26 The arrangement of 54 points which cannot be covered by unit disks.. 各格子を用いて求められた PU より PU0 を求め，さらに改善された上界を求めた結果を表. 2 に，三角格子により求められた 54 個の上界を図 26 に示す．. 5. まとめ本論文では，複数の単位円による点集合の排他的被覆問題において，どんな配置でもすべての点を必ず覆うことができる点の個数 k の上界と下界の改善ができないか計算機実験と考察を行った．上界については計算機実験により 54 個に改善することができた．今後は，別の手法を用いて，上界の改善を行えないか考察していくことが課題としてあげられる．. 参. 考. 文. 献. 1) 稲葉直樹：10 個の点，http://puz.hp.infoseek. co.jp/hirameki/suuri 4.html, 2009. 2) 上原隆平：私信，2010. 3) 斉藤浩：確率パズルにだまされるな！（その 3），理系への数学，現代数学社，Vol.44, No.2, pp11–14(2011). 4) Veit E.: Packing-constrained point coverings, manuscript, 2011.. 表 2 各格子により求められた上界 2 Table 2 The number of points which cannot be covered by unit disks based on each lattice. 格子の種類. 求められる上界. 正方格子改善した正方格子三角格子六角格子. 75 73 54 78. 8. c 2011 Information Processing Society of Japan.

(9)