空間充填曲線

空間充填曲線とは、その像が高次元の領域を覆う連続写像のことです。これは物理的な太さを持つ線ではなく、その結果は無限の数学的極限に属するものです。

ヒルベルト曲線の最初の3次の項は、極限過程において1次元の直線が正方形をどのように密に横断するかを示しています。画像: Geoff Richards (Qef) · Wikimedia Commons · Public Domain

ペアーノの驚き

1890において、ジュゼッペ・ペアノは、区間から正方形への連続的な全射の最初の構成を示しました。ヒルベルトはまもなく、幾何学的に明快な再帰的なバージョンを提示し、その多角形による近似は、ますます細かい格子点を順次訪れていきます。

ペアノの写像は、単位区間から正方形への連続かつ全射な写像です。これは中間値定理と矛盾するものではなく、連続性が次元を保存するという素朴な期待と矛盾するものです。有限近似は所定の順序で次第に細かいセルを順に訪れますが、すべての点に到達するのは、その一様極限写像のみです。また、この写像は一対一ではない必要があります。つまり、複数のパラメータ値が正方形内の同じ点を表す可能性があるからです。

次元については、文脈に応じて適切に判断してください

定義域は位相論的な意味において1次元の区間であるのに対し、画像は2次元の正方形を覆っています。したがって、空間充填曲線は、位相、測度、スケーリング次元が互換性のあるものとして扱えない理由を示しています。

パラメータ領域の位相次元は1である一方、その像は2次元の領域です。したがって、議論の対象となる定義や対象物に応じて、正しい次元は異なります。有限多角形による近似は、すべて依然として通常の直線として振る舞い、極限においてのみ領域が埋められます。この例は、特にパラメータ、像、近似が1つの図に示されている場合、対象物や定義を特定せずに「次元」という表現を用いることへの注意を促しています。

実用的な利点としての「局所性」

有限ヒルベルト順序および関連する順序は、1次元方向の探索において、近隣のグリッドセルを互いに近接させたままにする傾向があります。この特性により、空間インデックス作成、キャッシュを意識した処理、画像アルゴリズムにおいて有用ですが、実際の実装では、数学的な限界には程遠い段階で停止することが一般的です。

ヒルベルト順序やモートン順序には実用的な価値があります。なぜなら、順序付けに沿った近接した位置は、多くの場合、空間的に近接したセルに対応するからです。この保存性は完全ではありませんが、キャッシュ、データベース、画像処理において有用です。2次元のタイルセットは、メモリ間を繰り返し移動することなく、1次元のシーケンスとして処理できます。こうして、歴史的な珍事であったものが、現代のストレージ階層における具体的な戦略へと変貌を遂げたのです。