Aug 17, 2026約6分で読めます

ランダムに撒いた400点を「自分の縄張りの重心」へ動かし続けたら、六角形の割合が31.4%から69.2%になった

平面に点をいくつか置いて、それぞれの点に「自分がいちばん近い領域」を割り当てる。できあがる分割がボロノイ図だ。

携帯電話の基地局のカバー範囲、キリンの模様、細胞の並び、最寄り駅の勢力圏。どれも同じ骨格を持っている。定義は「最も近い点はどれか」だけで、それ以上の指定はない。

このボロノイ図に、ひとつ操作を加える。各点を、自分の縄張りの重心へ動かす。 これを繰り返す(Lloyd法、あるいはボロノイ緩和)。ランダムに撒いた点が、蜂の巣のような規則的な配置に整っていくことが知られている。

どれくらい整うのか。何回で止まるのか。測った。

実験に使ったコードの全文はGitHubに置いています。

400点を40回動かす

単位正方形にランダムな400点を撒き、 $600 \times 600$ の格子で各点の縄張りを求めて、重心へ動かす。

ランダムに撒かれた点のボロノイ図が、繰り返しのたびに整っていくアニメーション。最初はセルの大きさも形もばらばらだが、回を重ねるごとに大きさが揃い、六角形に近い形が増えていく

段階を並べるとこうなる。

4枚のボロノイ図を2×2に並べた図。0回目はセルの大きさがばらばらで細長い形も多い。2回目、10回目と進むにつれて揃っていき、40回目はほぼ均一な大きさの六角形が並ぶ蜂の巣状になっている。それぞれに面積のばらつきの数値が書かれている

セル面積の変動係数(標準偏差÷平均)を追うと、こうなった。

40回で5分の1になる。ただし急激に減るのは最初の数回で、そこから先はゆっくりだ。

左は繰り返し回数に対するセル面積の変動係数のグラフで、0.540から急降下して0.108へ、後半はなだらかになる。右は各セルが持つ辺の数の分布を比較した棒グラフで、ランダム直後(灰)は4辺から9辺まで広く散らばるが、40回後(赤)は6辺に大きく集中している

形のほうも変わる。六角形(辺が6本のセル)の割合は 31.4% → 69.2%。平均辺数は5.896から5.991になった。

ここで気になることがある。「六角形が増える」なら、平均辺数はどこまで上がるのか。

答えは6で、しかもこれは実験でどうこうなる数字ではない。平面を多角形で隙間なく分割すると、オイラーの多面体定理から、辺の平均は6に収束することが決まっている。ランダムな点でも、整えた点でも変わらない。

実測でも確かめた(外周に接するセルは除いてある)。

点の数を横軸(対数)、1セルあたりの平均辺数を縦軸にしたグラフ。100点で5.777、300点で5.908、1000点で5.939、3000点で5.962、10000点で5.977と、理論値6の破線に下から近づいていく

下から6に近づき、超えない。点の数を増やすほど外周の影響が薄まって、6に寄っていく。

つまりLloyd法がやっているのは「平均辺数を増やすこと」ではない。平均は最初から6の近くにある。変わっているのは分布のばらつきだ。4角形や8角形が減って6角形に集まる。平均は動かないまま、山だけが尖る。

ボロノイ図の定義は「最も近い点」だが、「近い」の測り方は1つではない。同じ60点に対して3種類の距離で縄張りを描いた。

3枚のボロノイ図を縦に並べた図。上のユークリッド距離は直線で区切られた普通の多角形、中央のマンハッタン距離は45度の折れ線を含む階段状の境界、下のチェビシェフ距離は水平・垂直の折れ線が目立つ角ばった境界になっている。同じ60個の黒い点が3枚とも同じ位置に打たれている

見た目はかなり違う。ユークリッド距離では境界が直線になるが、マンハッタン距離では45度の折れ線が混じり、チェビシェフ距離では水平・垂直の段差が目立つ。

一方で面積のばらつきはほとんど変わらない(0.554〜0.576)。縄張りの形は距離の定義で決まるが、大きさの偏りは点の配置で決まっていた。

なお、この「各点を自分の縄張りの重心へ動かす」という手続きは、k-means++の回で扱ったk-means法そのものだ。あちらはデータ点を分類する道具として、こちらは点を整える道具として使っているが、動いている式は同じものになる。

平均は最初から6で、40回動かしても5.99だった。動いたのはばらつきのほうだけだ。

この構図は、数字を見るときに何度もやってしまう取り違えだと思う。「平均辺数6」という数字は、正六角形が敷き詰められた蜂の巣を思い浮かべさせる。だが実際には、4角形と8角形が混じった雑然とした分割でも平均は6になる。平均が理論値と一致していることは、中身が理論通りであることを何も保証しない。

Lloyd法の効果を測ろうとして最初に平均辺数を見たとき、5.896から5.991という差にがっかりした。0.1しか動いていない。分布を描いてやっと、31.4%が69.2%になっていたことが分かった。

見るべき数字を最初から知っていたわけではなくて、平均が動かないと分かってから、次に何を見ればいいかを考えた。

新着記事をお届け

noteをフォローすると、新しい記事の更新をタイムラインで受け取れます。

このブログでは、機械学習の仕組みを実際にコードで実装して確かめた実験をテーマ別に整理しています（拡散モデル・Transformer・強化学習・多様体学習・過学習など）。