Крива Гільберта

Перші 8 кроків створення кривої Гільберта

Крива Гільберта (відома також як крива Гільберта, що заповнює простір) — це неперервна фрактальна крива, що заповнює простір, вперше описана німецьким математиком Давидом Гільбертом у 1891 році, як варіант кривих Пеано, що заповнюють простір, відкритих італійським математиком Джузеппе Пеано в 1890 році.

Оскільки крива заповнює площину, її розмірність Гаусдорфа дорівнює $2$ (її образ є одиничним квадратом, розмірність якого дорівнює 2 при будь-якому визначенні розмірності, а її граф є компактною множиною, гомеоморфною замкнутому одиничному інтервалу з розмірністю Гаусдорфа 2) .

$H_{n}$ є $n$-м наближенням до граничної кривої. Евклідова довжина кривої $H_{n}$ дорівнює $\textstyle 2^{n}-{1 \over 2^{n}}$, тобто росте експоненціально з $n$, в той же час сама крива завжди лишається в межах квадрата зі скінченною площею.

Застосування

На основі кривої Гільберта можуть бути реалізовані вібраторні або друковані конструкції антен.

Відомі застосування кривої Гільберта для стискання баз даних. Завдяки властивості локальності крива Гільберта використовується в комп'ютерних програмах, наприклад, для візуаліазції діапазону IP-адрес, присвоєних комп'ютерам.

Рисунки

• 
  Крива Гільберта, перший крок
• 
  Крива Гільберта, перший і другий крок
• 
  Криві Гільберта, з першого по третій кроки
• 
  Ниткова графіка
• 
  Крива Гільберта у кольорі

• 
  Тривимірна крива Гільберта
• 
  Тривимірна крива Гільберта у кольорі, що вказує послідовність
• 
  Анімаційна ілюстрація, що показує проходження кружків кривою.

Див. також

• Крива Мура
• Крива Мінковського

Джерела

• I. Kamel, C. Faloutsos. Hilbert R-tree: An improved R-tree using fractals // Proceedings of the 20th International Conference on Very Large Data Bases / Jorge Bocca, Matthias Jarke, Carlo Zaniolo. — San Francisco, CA, USA : Morgan Kaufmann Publishers Inc, 1994. — ISBN 1-55860-153-8.
• G.Peano. Sur une courbe, qui remplit toute une aire plane. // Mathematische Annalen. — 1890. — Вип. 36.
• D. Hilbert. Über die stetige Abbildung einer Linie auf ein Flächenstück. // Mathematische Annalen. — 1891. — Вип. 38.
• A.R. Butz. Alternative algorithm for Hilbert’s space filling curve. // IEEE Trans. On Computers. — 1971. — Т. 20. — DOI:10.1109/T-C.1971.223258.
• B. Moon, H.V. Jagadish, C. Faloutsos, J.H. Saltz. Analysis of the clustering properties of the Hilbert space-filling curve // IEEE Transactions on Knowledge and Data Engineering. — 2001. — Т. 13, вип. 1. — DOI:10.1109/69.908985.
• I. Kamel, C. Faloutsos. Proceedings of the 20th International Conference on Very Large Data Bases. — San Francisco, CA, USA, 1994.
• T. Eavis, D. Cueva. A Hilbert space compression architecture for data warehouse environments // Lecture Notes in Computer Science. — 2007. — Т. 4654.
• Daniel Lemire, Owen Kaser. Reordering Columns for Smaller Indexes // Information Sciences. — 2011. — Т. 181, вип. 12. — arXiv:0909.1346.
• C. H. Hamilton, A. Rau-Chaplin. Compact Hilbert indices: Space-filling curves for domains with unequal side lengths // Information Processing Letters. — 2007. — Т. 105, вип. 5. — DOI:10.1016/j.ipl.2007.08.034.
• J. Alber, R. Niedermeier. On multidimensional curves with Hilbert property // Theory of Computing Systems. — 2000. — Т. 33, вип. 4. — DOI:10.1007/s002240010003.
• H. J. Haverkort, F. van Walderveen,. Four-dimensional Hilbert curves for R-trees // Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments. — New York : Society for Industrial and Applied Mathematics ( SIAM ), 2009. — ISBN 9781615671489.
• Douglas Voorhies. Space-Filling Curves and a Measure of Coherence / Andrew S. Glassner. — Boston, San Diego, New York, London, Sydney, Tokyo, Toronto : AP Professional, 1991. — Т. II. — (Graphics Gems) — ISBN 0-12-059756-X.

Посилання

• Dynamic Hilbert curve with JSXGraph
• Three.js WebGL 3D Hilbert curve demo
• XKCD cartoon using the locality properties of the Hilbert curve to create a «map of the internet»
• Gcode generator for Hilbert curve