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

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

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

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

є -м наближенням до граничної кривої. Евклідова довжина кривої дорівнює , тобто росте експоненціально з , в той же час сама крива завжди лишається в межах квадрата зі скінченною площею.

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

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

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

Рисунки

Див. також

Примітки

  1. Hilbert, 1891, с. 459—460.
  2. Peano, 1890, с. 157—160.
  3. Слюсар, В. (2007). Фрактальные антенны. Принципиально новый тип «ломаных» антенн. Часть 2.. Электроника: наука, технология, бизнес. — 2007. — № 6. с. С. 82—89.
  4. Eavis, Cueva, 2007, с. 1—12.
  5. Lemire, Kaser, 2011.

Джерела

  • 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.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.