読者です 読者をやめる 読者になる 読者になる

roombaの日記

読書・非線形科学・プログラミング・アート・etc...

球充填のボロノイ・セルを視覚的に理解する

はじめに

ケプラー予想に関する本を先日読みました。ケプラー予想とは、ザックリと言えば「球を最も効率よく詰め込む方法は、果物屋がオレンジを積む方法*1と同じ」という予想です。ちょっとオレンジを積んでみれば誰でも思い付くような配置なので、予想自体は誰もが当然と思うような内容なのですが、その証明には400年もの歳月が必要だったそうな。

ケプラー予想: 四百年の難問が解けるまで (新潮文庫―Science&History Collection)

ケプラー予想: 四百年の難問が解けるまで (新潮文庫―Science&History Collection)

この本にはケプラー予想に対する様々なアプローチが紹介されており、その中に「ボロノイ・セル」なるものに関する以下のような記述があります。

球による最密充填のボロノイ・セルは菱形十二面体になる

そんなことを言われても……という感じですよね。それをイメージ出来るようにしようというのが本記事の内容です。
画像を眺めるだけでもなんとなく分かると思うので、ぜひ読み進めてください。


ボロノイ・セルとは?

例えば携帯電話の基地局がいくつもあり、それぞれの位置が地図上で分かっているとしましょう。このとき、「どの基地局に最も近いか」に応じて地図を塗り分けたものを「ボロノイ図」と呼び、それぞれの領域を「ボロノイ領域」あるいは「ボロノイ・セル」と呼びます。
ボロノイ図 - Wikipedia

ボロノイ図の例を以下に示しました。色分けされた各多角形がボロノイ・セルです。
f:id:roomba:20150710203829p:plain
"Coloured Voronoi 2D". Licensed under CC BY-SA 3.0 via Wikimedia Commons.

2次元(円充填)のボロノイ・セル

ケプラー予想は球をぎっしりと並べる方法に関するものですが、まずは次元を2次元に下げて、をぎっしりと並べる方法を考えてみましょう。コインを並べればすぐわかるように、以下の並べ方が最も効率の良い並べ方です。
f:id:roomba:20150711153349j:plain
このとき、それぞれの円の中心によって構成されるボロノイ図は下図の太線(正六角形が並んだ蜂の巣状のもの)のようになります。
f:id:roomba:20150710203828j:plain
ボロノイ・セルは各円に外接する正六角形となり、充填密度はボロノイ・セルと円の面積比を求めることで
{ \displaystyle
\frac{\pi}{\sqrt{12}} \simeq 0.9069
}
と計算することができるわけです。

3次元(球充填)のボロノイ・セル

2次元(円充填)の場合は分かったので、いよいよ球充填のボロノイ・セルに移りましょう。球が最も密に並べられているとき、各球の中心によって構成されるボロノイ図を考えます。3次元でも今までと考え方は同じですが、ボロノイ・セルは多角形ではなく多面体になります。

ボロノイ・セルの形状

結論から言うと、冒頭で触れたように、球をもっとも密に充填する場合のボロノイ・セルは菱形十二面体(りょうけいじゅうにめんたい、rhombic dodecahedron)となります。
聞きなれない名前ですが、下図のようにひし形の面が12個ある多面体です。
f:id:roomba:20150710203821j:plain
(図は3次元CADで作成しました。以下、引用の表示がない画像はCADのスクリーンショットに基づきます。)

この菱形十二面体に内接するように球を収めると、下図のようになります。このような「菱形十二面体 + 内接する球」を並べていくと、いつの間にか球の配置が最密充填になるのです。
f:id:roomba:20150710203822j:plain

ボロノイ・セルを並べると?

では、この「菱形十二面体 + 内接する球」を並べましょう。菱形十二面体には、空間を隙間なく埋め尽くすことができるという性質があります。

4つ並べると以下のようになり、……
f:id:roomba:20150710203817j:plain

たくさん並べると以下のようになります。「果物屋がオレンジを積む方法」になっていそうですね。
f:id:roomba:20150710203823j:plain
ボロノイ・セルを並べることで最密充填になることが分かりました。

ボロノイ・セルを考える利点

ここまでで、最密充填のときのボロノイ・セルが菱形十二面体になっていることが分かったかと思います。以下では、最密充填に対してボロノイ・セルを考えることで、

  • 最密充填時に、1つの球の周りにはいくつの球が接しているかがすぐに分かる
  • 最密充填を眺める2つの視点を身に着けることができる
  • 最密充填の充填率が計算できる

という利点があることを紹介します。

最密充填時の隣人の数

最密充填のときに1つの球の周りにはいくつの球が接しているでしょうか?
……ボロノイ・セルが12面体であることを考えれば、答えは12であるとすぐにわかりますね!

実際に1つの球のまわりに12個の球を並べた図を以下に示します。
f:id:roomba:20150710203818j:plain

球充填を眺める2つの角度

すぐ上の「1つの球のまわりに12個の球を並べた図」は、見る向きによって以下のように2通りの見え方が存在します。

向きA↓
f:id:roomba:20150710203820j:plain

向きB↓
f:id:roomba:20150710203819j:plain

ここで、向きAは
4つの球の上に1つの球を積んでいったもの」
を上から見たような図になっているのに対し、向きBでは
3つの球の上に1つの球を積んでいったもの」
を上から見たような図になっています。これらは別々の積み方に思えますが、実は同一の積み方を別方向から見たものだったのです!!
そのような2種類の見方ができるのは、向きAではボロノイ・セルが正方形に見えるのに対し、向きBではボロノイ・セルが正六角形に見えることから理解することができるのです。

参考までに、菱形十二面体を2つの方向から見た図を以下に用意しました。
f:id:roomba:20150711153350j:plain

ボロノイ・セルを用いた充填率の計算

最後に、ボロノイ・セルを用いた充填率の計算方法を記しておきます。高校化学では「単位格子」なるものに対して球の占める割合を計算することで充填率を求めるのですが、ボロノイ・セルを用いて計算することもできるのです。

まず、充填率は「ボロノイ・セルの体積(Vvとします)に対する球の体積(Vsとします)の割合」、すなわち
{ \displaystyle
\frac{V_s}{V_v}\:\:\:\:\:\:(1)
}
であることに注目しましょう。球の半径をrとすれば
{ \displaystyle
V_s = \frac{4 \pi r^3}{3}\:\:\:\:\:\:(2)
}
とすぐに求められるので、あとは菱形十二面体の体積Vvを計算すればよいことになります。

ここで、下図の赤い正方形を考えましょう。
f:id:roomba:20150710203826p:plain
この正方形の一辺の長さは内接球の直径に等しいため、2rです。
また、各菱形の形状は下図のようになっているため、菱形の面積をSとすると
{ \displaystyle
S = \frac{1}{2} \times 2r \times \sqrt{2} r = \sqrt{2} r^2 \:\:\:\:\:\:(3)
}
と求められます。
f:id:roomba:20150710203827p:plain

菱形十二面体のボロノイ・セルの体積は、底面をこの菱形とする12個の錐体に分割して考えることにより、以下のように求めることができます。各錐体の高さが内接球の半径rに等しいことがポイントです。
{ \displaystyle
V_v = 12 \times \frac{1}{3} \times S \times r = 4Sr \:\:\:\:\:\:(4)
}
式(3)のSを式(4)に代入すると、菱形十二面体のボロノイ・セルの体積は以下のようになりました。
{ \displaystyle
V_v = 4Sr = 4 \times \sqrt{2} r^2 \times r = 4\sqrt{2} r^3 \:\:\:\:\:\:(5)
}

ここまでくると、充填率は式(1)のVsとVvに式(2), 式(5)を代入して
{ \displaystyle
\frac{V_s}{V_v} = \frac{\frac{4 \pi r^3}{3}}{4\sqrt{2} r^3} = \frac{\pi}{3\sqrt{2}} \simeq 74 (\%)
}
と求められます。めでたしめでたし。

おわりに

ボロノイ・セルを考えることによって、球充填をより深く理解することができました。
なお、最密ではない充填の場合、ボロノイ・セルが立方体になったり正六角柱になったりします。それはどのような配置の場合でしょうか? 暇な方は考えてみてください。さらに暇な方は、その場合の充填率も計算してみてくださいね。筆者はもう疲れました。

なお、ケプラー予想の本は6月に読みました。他に読んだ本は↓に挙げてあります。roomba.hatenablog.com

*1:高校化学で学ぶ「面心立方格子構造」「六方最密充填」