空間充填曲線をわかりやすく解説
線は一次元で、正方形は二次元です。だから、線が正方形を覆うことなどありえないのは明らかに思えます。ところが1890年、ジュゼッペ・ペアノは、それが可能であることを示しました。正方形のすべての点を通る連続な曲線が存在するのです。この発見によって数学者たちは、曲線とは何か、次元とは何かを考え直さざるをえなくなりました。そして一世紀後、同じ曲線がコンピューターの中で、地図や画像のデータを整然と並べています。
正方形と同じだけの点
1877年、ゲオルク・カントールは、線分には正方形とちょうど同じだけの点があることを証明しました。正方形のどの点にも、線分上のその点だけの相手を対応させられるのです。彼はリヒャルト・デデキントにこう書き送りました。「私にはそれが見えるが、信じられない」。しかし、カントールの対応づけは、でたらめに飛び回ります。線を引き裂いて塵にしてしまうのです。残された問いは、線を引き裂くことなく、つまり連続的に、正方形を覆えるかどうかでした。
ペアノ曲線
1890年、イタリアの数学者ジュゼッペ・ペアノがその答えを出しました。できる、というのです。彼は、図を一枚も使わず数式だけで、単位正方形のすべての点を通る連続な曲線を記述しました。その構成では、正方形を9つの小さな正方形に分け、S字の折れ曲がりを描きながらそれらを順にたどり、同じことをそれぞれの小さな正方形の中で、何度も何度も繰り返します。
ヒルベルトの図
その翌年、ダフィット・ヒルベルトが、より単純な構成を、この考えを目に見えるものにした図とともに発表しました。正方形を4つに分け、その中心を一本の折れ曲がった線で結びます。次に、小さな正方形をそれぞれ4つに分けて同じことを繰り返し、線が一つの複製から次の複製へと続くように、小さな複製の向きを変えます。レベル n の曲線は 4ⁿ 個のマスを通ります。正方形を埋めるのは、すべてのレベルの極限です。1900年には、エリアキム・ヘイスティングス・ムーアが、始点に戻って終わる変種、つまり閉じたループを与えました。
極限がうまくいく理由
線上の一点、たとえば全体の三分の一だけ進んだところにある点を追いかけてみましょう。レベル1では、この点は4つのマスのどれか一つの中にあります。レベルが上がるたびに点は動きますが、そのマスの中にとどまり、次にはその四分の一の中に、というように、一辺が毎回半分になるマスの中にとどまり続けます。そのため点の位置は落ち着いていき、同じことが線上のすべての点について成り立ちます。極限は連続な曲線です。そして、どのレベルも、ますます細かくなるグリッドのすべてのマスを通るので、極限の曲線は正方形のどの点にもいくらでも近づき、連続であるがゆえに、その点に到達します。
一対一にはできない
空間充填曲線には、支払わなければならない代償があります。1879年にオイゲン・ネットーが、線を正方形の上へ連続かつ一対一に写すことはできないと証明しました。したがって曲線は、いくつかの点を二度以上通らなければなりません。ヒルベルト曲線は、点によっては最大で四度通ります。また、どこでも滑らかではありません。どの点でも接線をもたないのです。
長さと次元
レベル n のヒルベルト曲線の長さは正方形の一辺の 2ⁿ − 2⁻ⁿ 倍で、一つ前のレベルのおよそ二倍です。長さには限りがありませんが、曲線が正方形の外に出ることは決してありません。大きさが半分の自分自身の複製4つからできている曲線の次元は log 4 / log 2 = 2 で、曲線が埋める正方形の次元と同じです。ペアノ曲線は、大きさが三分の一の複製9つからできていて、こちらも log 9 / log 3 = 2 です。
隣どうしを近くに保つ
ヒルベルト曲線には、役に立つ性質があります。線の上で近くにある点は、正方形の中でも近くに来るのです。逆はいつも成り立つとはかぎりません。隣り合う二つのマスが、線の上では遠く離れていることもあります。コンピューターはこの曲線を使って、地図タイル、ピクセル、地球上の場所といった二次元のデータを、隣どうしの大半を近くに保つ一次元の順序で保存します。1966年にIBMのガイ・モートンが記述したZオーダーは、二つの座標のビットを交互に並べることで同じ役目を果たします。計算は速いのですが、ジャンプするので、隣どうしを近くに保つ力は劣ります。
ゴスパーの flowsnake とシェルピンスキーの矢じり曲線
すべての空間充填曲線が正方形を埋めるわけではありません。ビル・ゴスパーの1973年の曲線は、1976年にマーティン・ガードナーが紹介して以来 flowsnake の名で知られ、三角形のグリッドの上を、線分一つにつき七つの線分で進みます。この曲線が埋めるのは、フラクタルな海岸線をもつ形、ゴスパー島で、それを七つ合わせると、より大きなゴスパー島になります。ヴァツワフ・シェルピンスキーの矢じり曲線は、一見よく似ていますが、線分一つにつき大きさが半分の部分が三つしかないため、何も埋めません。次元が log 3 / log 2 ≈ 1.585 のシェルピンスキーの三角形をなぞるのです。
試してみましょう
空間充填曲線エクスプローラーを開いて「再生」を押すと、ペンがヒルベルト曲線の各レベルを始点から終点まで描いていく様子を見られます。ペアノのS字の折れ曲がり、ムーアの閉じたループ、ジャンプするZオーダー、ゴスパーの flowsnake、矢じり曲線に切り替えてみましょう。曲線上の好きな場所、あるいは図の下の数直線の上にペンを置いて、どのステップがどのマスに入るかを確かめ、「前のレベルを表示」をオンにして、一つひとつのステップがまるごと一つの折れ曲がりに変わる様子を見てください。
よくある質問
最初の空間充填曲線を発見したのは誰ですか?
ジュゼッペ・ペアノで、1890年のことです。そのため、空間充填曲線はペアノ曲線とも呼ばれます。最もよく知られているのは1891年のダフィット・ヒルベルトの曲線で、それはヒルベルトがこの構成を初めて図に描いたからです。
空間充填曲線はフラクタルですか?
作り方はフラクタルと同じで、自分自身の小さな複製からできています。しかし、完成した曲線は面積を覆うので、そのフラクタル次元は 2 という整数になります。次元が約 1.585 のシェルピンスキーの矢じり曲線は、ふつうの意味でのフラクタルです。
ヒルベルト曲線の長さはどれくらいですか?
レベル n の長さは正方形の一辺の 2ⁿ − 2⁻ⁿ 倍です。レベル1では 1.5、レベル4では 15.94、レベル8ではほぼ 256 になります。極限の曲線は無限の長さをもちます。
エクスプローラーは何レベルまで描けますか?
ヒルベルト曲線、ムーア曲線、Zオーダーはレベル8までで、これは 256 × 256 個のマスからなるグリッドにあたります。ペアノ曲線(243 × 243 個のマス)とゴスパー曲線(線分 16,807 本)はレベル5まで、シェルピンスキーの矢じり曲線はレベル10まで(線分 59,049 本)です。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
空間充填曲線エクスプローラーを開く