PROFILPELAJAR.COM

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

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

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

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

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

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

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

Рисунки

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

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

Див. також

Примітки

↑ Hilbert, 1891, с. 459—460.
↑ Peano, 1890, с. 157—160.
↑ Слюсар, В. (2007). Фрактальные антенны. Принципиально новый тип «ломаных» антенн. Часть 2 (PDF). Электроника: наука, технология, бизнес. — 2007. — № 6. с. С. 82—89. Архів оригіналу (PDF) за 3 квітня 2018. Процитовано 22 квітня 2020. {{cite web}}: |pages= має зайвий текст (довідка)
↑ Eavis, Cueva, 2007, с. 1—12.
↑ 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.