ヒルベルト曲線

ヒルベルト曲線（ヒルベルト空間充填曲線とも呼ばれる）は、1890年にジュゼッペ・ペアノが発見した空間充填ペアノ曲線の変形として、1891年にドイツの数学者デイヴィッド・ヒルベルトによって初めて記述された連続フラクタル空間充填曲線である。 [ ^{1 ]}

これは空間充填なので、ハウスドルフ次元は 2 です (正確には、その像は単位正方形であり、その次元はどの次元の定義でも 2 です。そのグラフは、閉じた単位区間に同相なコンパクト セットであり、ハウスドルフ次元は 1 です)。

ヒルベルト曲線は、区分線形曲線の極限として構築されます。 番目の曲線の長さはです。つまり、各曲線が面積 の正方形に含まれる場合でも、長さは とともに指数的に増加します。 ${\displaystyle n}$${\displaystyle \textstyle 2^{n}-{1 \over 2^{n}}}$${\displaystyle n}$${\displaystyle 1}$

• 
  ヒルベルト曲線、一次
• 
  ヒルベルト曲線、1次と2次
• 
  ヒルベルト曲線、1次から3次
• 
  制作ルール
• 
  ヒルベルト曲線、構成は色分けされています
• 
  進行を示す色付きの3Dヒルベルト曲線
• 
  バリアント、最初の3つの反復^[3]

真のヒルベルト曲線とその離散近似はどちらも、局所性をかなりよく保った1次元と2次元空間間のマッピングを提供するため有用である。^[4] これは、1次元空間で互いに近い2つのデータポイントは、折り畳み後も互いに近いことを意味します。逆は常に真であるとは限りません。

この局所性特性のため、ヒルベルト曲線はコンピュータサイエンスで広く使用されています。たとえば、コンピュータで使用されるIP アドレスの範囲は、ヒルベルト曲線を使用して画像にマッピングできます。画像を生成するコードは、各ピクセルの色を見つけるために 2D から 1D にマッピングしますが、ヒルベルト曲線は、近くの IP アドレスを画像内で互いに近くに保つため、使用されることがあります。^[5]ヒルベルト曲線の局所性特性は、移動ロボットで領域を探索するためのアルゴリズムの設計にも使用されています。^{[6] [7]}

リーマースマディザリングと呼ばれるアルゴリズムでは、しきい値処理を使用してグレースケールの写真をディザリングされた白黒画像に変換し、各ピクセルの残りの量をヒルベルト曲線に沿って次のピクセルに追加することができます。これを行うコードは 1D から 2D にマッピングされ、ヒルベルト曲線は、ピクセルの各行を単純に左から右に並べた場合に目に見える邪魔なパターンを作成しないため、使用されることがあります。^{[8]より高次元のヒルベルト曲線は、}グレイコード の一般化の例であり、同様の理由で同様の目的で使用されることがあります。多次元データベースでは、局所性保存動作が優れているため、 Z 順序の代わりにヒルベルト順序を使用することが提案されています。たとえば、ヒルベルト曲線は、R ツリーインデックスの圧縮と高速化に使用されています^[9] (ヒルベルト R ツリーを参照)。また、データウェアハウスの圧縮にも使用されています。^{[10] [11]}

曲線上の任意の点の直線距離は、スキルリング法などのいくつかの標準的な数学的手法を使用して、与えられたnに対してn次元の座標に変換することができ、逆もまた同様である。^{[12] [13]}

データ空間が正方形を形成しない場合でも、ヒルベルト曲線を効率的に実装することは可能です。^[14]さらに、ヒルベルト曲線を高次元に一般化することは可能です。^{[15] [16]}

ヒルベルト曲線は書き換えシステム（Lシステム）で表現できます。

アルファベット ：A、B

定数 : F + −

公理 ：A

制作ルール：

A → +BF−AFA−FB+

B → −AF+BFB+FA−

ここで、「F」は「前方に描画」を意味し、「+」は「左に 90 度回転」を意味し、「-」は「右に 90 度回転」を意味します (タートル グラフィックスを参照)。また、「A」と「B」は描画中に無視されます。

Graphics Gems II ^{[17] [プロモーション? ]では}ヒルベルト曲線の一貫性について説明し、実装を提供しています。

ヒルベルト曲線は、画像やビデオのレンダリングでよく使用されます。BlenderやCinema 4Dなどの一般的なプログラムは、ヒルベルト曲線を使用してオブジェクトをトレースし、シーンをレンダリングします。^{[引用が必要]}

3D モデルを3D プリンターのツールパスに変換するために使用されるスライサー ソフトウェアには、通常、充填パターンのオプションとしてヒルベルト曲線があります。

ウィキメディア・コモンズにはヒルベルト曲線に関連するメディアがあります。

• ヒルベルト曲線スケジューリング
• ヒルベルト R 木
• 参照の地域
• 局所性を考慮したハッシュ
• ムーア曲線
• マレーポリゴン
• シェルピンスキー曲線
• ハウスドルフ次元によるフラクタルのリスト

• ウォーレン・ジュニア、ヘンリー・S. (2013)。Hacker 's Delight (第2版)。Addison Wesley – Pearson Education, Inc. ISBN 978-0-321-84268-8。
• マッケナ、ダグラス M. (2019)。ヒルベルト曲線：外から内へ、そして内から消えた。Mathemaesthetics, Inc. ISBN 978-1-7332188-0-1。

• JSXGraph による動的ヒルベルト曲線
• Three.js WebGL 3D ヒルベルト曲線デモ
• ヒルベルト曲線の局所性特性を利用して「インターネットの地図」を作成する XKCD 漫画
• ヒルベルト曲線の Gcode ジェネレーター 2019-07-09 にWayback Machineでアーカイブされました
• JavaScript でヒルベルト曲線を描く反復アルゴリズム
• アルゴリズム 781: 再帰によるヒルベルトの空間充填曲線の生成 (ACM デジタル ライブラリ)