Curva de Hilbert

A curva de Hilbert (também conhecida como a curva de preenchimento de espaço de Hilbert) é uma curva fractal contínua que preenche o espaço, descrita pela primeira vez pelo matemático alemão David Hilbert em 1891, como uma variante das curvas de Peano que preenchem o espaço, descobertas por Giuseppe Peano em 1890.

Por ser uma curva de preenchimento de espaço, sua dimensão de Hausdorff é 2 (precisamente, sua imagem é o quadrado unitário, cuja dimensão é 2 em qualquer definição de dimensão; seu gráfico é um conjunto compacto homeomórfico ao intervalo unitário fechado, com dimensão de Hausdorff 2).

A curva de Hilbert é construída como um limite de curvas linearmente segmentadas. O comprimento da $n$ -ésima curva é $\textstyle 2^{n}-{1 \over 2^{n}}$ , i.e., o comprimento cresce exponencialmente com $n$ , mesmo que cada curva esteja contida num quadrado de área $1$ .

Imagens

Curva de Hilbert, primeira ordem
Curvas de Hilbert, primeira e segunda ordem
Curvas de Hilbert, primeira a terceira ordem
Regras de produção
Curva de Hilbert, construção codificada em cor
Uma curva de Hilbert 3-D com cores mostrando a progressão
Variante, primeiras três iterações

Aplicações e algoritmos de mapeamento

Tanto a verdadeira curva de Hilbert quanto suas aproximações discretas são úteis porque fornecem um mapeamento entre o espaço 1D e 2D que preserva a localidade de forma bastante eficaz.^[1] Isso significa que dois pontos de dados que estão próximos um do outro no espaço unidimensional também estão próximos um do outro após o dobramento. O inverso nem sempre pode ser verdadeiro.

Devido a essa propriedade de localidade, a curva de Hilbert é amplamente utilizada na ciência da computação. Por exemplo, o intervalo de endereços IP usado por computadores pode ser mapeado em uma imagem usando a curva de Hilbert. O código para gerar a imagem mapearia de 2D para 1D para encontrar a cor de cada pixel, e a curva de Hilbert é às vezes usada porque mantém endereços IP próximos uns dos outros na imagem.^[2] A propriedade de localidade da curva de Hilbert também foi usada para projetar algoritmos para explorar regiões com robôs móveis.^[3]^[4]

Em um algoritmo chamado dithering de Riemersma, fotografias em escala de cinza podem ser convertidas em uma imagem binária com dithering usando a limiarização, com a quantidade restante de cada pixel adicionada ao próximo pixel ao longo da curva de Hilbert. O código para fazer isso mapearia de 1D para 2D, e a curva de Hilbert é às vezes usada porque não cria os padrões que seriam visíveis ao olho se a ordem fosse simplesmente da esquerda para a direita em cada linha de pixels.^[5] Curvas de Hilbert em dimensões superiores são uma instância de uma generalização de códigos Gray e são às vezes usadas para propósitos semelhantes, pelas mesmas razões. Para bancos de dados multidimensionais, a ordem de Hilbert foi proposta para ser usada em vez da ordem Z porque possui um comportamento de preservação de localidade melhor. Por exemplo, curvas de Hilbert foram usadas para comprimir e acelerar índices de árvores R^[6] (veja a árvore R de Hilbert). Elas também foram usadas para ajudar a comprimir data warehouses.^[7]^[8]

A distância linear de qualquer ponto ao longo da curva pode ser convertida em coordenadas em n dimensões para um dado n, e vice-versa, utilizando qualquer uma das várias técnicas matemáticas padrão, como o método de Skilling.

É possível implementar curvas de Hilbert de forma eficiente mesmo quando o espaço de dados não forma um quadrado.^[9] Além disso, existem várias generalizações possíveis das curvas de Hilbert para dimensões superiores.^[10]^[11]

Representação como um sistema de Lindenmayer

A Curva de Hilbert pode ser expressa por um sistema de reescrita (L-sistema).

Curva de Hilbert na sexta iteração

Alfabeto : A, B

Constantes : F + −

Axioma : A

Regras de produção:

A → +BF−AFA−FB+

B → −AF+BFB+FA−

Aqui, "F" significa "avançar", "+" significa "virar à esquerda 90°", "-" significa "virar à direita 90°" (veja gráficos de tartaruga), e "A" e "B" são ignorados durante o desenho.

Outras implementações

"Graphics Gems II"^[12] discute a coerência da curva de Hilbert e fornece implementação.

A Curva de Hilbert é comumente usada na renderização de imagens ou vídeos. Programas populares como Blender utilizam a Curva de Hilbert para traçar os objetos e renderizar a cena.^[^{carece de fontes?]}

Ver também

Agendamento de curva de Hilbert
Árvore R de Hilbert
Localidade de referência
Hashing sensível à localidade
Curva de Moore
Polígono de Murray
Curva de Sierpiński
Lista de fractais por dimensão de Hausdorff

Referências

↑ Moon, B.; Jagadish, H.V.; Faloutsos, C.; Saltz, J.H. (2001), «Analysis of the clustering properties of the Hilbert space-filling curve», IEEE Transactions on Knowledge and Data Engineering, 13 (1): 124–141, CiteSeerX 10.1.1.552.6697, doi:10.1109/69.908985 .
↑ «Mapping the whole internet with Hilbert curves». blog.benjojo.co.uk. Consultado em 2 de janeiro de 2021
↑ Spires, Shannon V.; Goldsmith, Steven Y. (1998), Drogoul, Alexis; Tambe, Milind; Fukuda, Toshio, eds., «Exhaustive geographic search with mobile robots along space-filling curves», ISBN 978-3-540-64768-3, Berlin, Heidelberg: Springer Berlin Heidelberg, Collective Robotics, 1456, pp. 1–12, doi:10.1007/bfb0033369, consultado em 14 de agosto de 2023
↑ Sadat, Seyed Abbas; Wawerla, Jens; Vaughan, Richard (2015). Fractal trajectories for online non-uniform aerial coverage. 2015 IEEE International Conference on Robotics and Automation (ICRA). pp. 2971–2976
↑ Thiadmer Riemersma (1 de dezembro de 1998). «A Balanced Dithering Technique». Dr. Dobb's. C/C++ User's Journal
↑ Thiadmer Riemersma (1 de dezembro de 1998). «A Balanced Dithering Technique». Dr. Dobb's. C/C++ User's Journal
↑ Eavis, T.; Cueva, D. (2007). «A Hilbert Space Compression Architecture for Data Warehouse Environments». Data Warehousing and Knowledge Discovery. Col: Lecture Notes in Computer Science. 4654. [S.l.: s.n.] pp. 1–12. ISBN 978-3-540-74552-5. doi:10.1007/978-3-540-74553-2_1
↑ Lemire, Daniel; Kaser, Owen (2011). «Reordering Columns for Smaller Indexes». Information Sciences. 181 (12): 2550–2570. arXiv:0909.1346. doi:10.1016/j.ins.2011.02.002
↑ Hamilton, C. H.; Rau-Chaplin, A. (2007). «Compact Hilbert indices: Space-filling curves for domains with unequal side lengths». Information Processing Letters. 105 (5): 155–163. doi:10.1016/j.ipl.2007.08.034
↑ Alber, J.; Niedermeier, R. (2000). «On multidimensional curves with Hilbert property». Theory of Computing Systems. 33 (4): 295–312. CiteSeerX 10.1.1.7.2039. doi:10.1007/s002240010003
↑ H. J. Haverkort, F. van Walderveen, Four-dimensional Hilbert curves for R-trees, in: Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009, pp. 63–73.
↑ Voorhies, Douglas: Space-Filling Curves and a Measure of Coherence, pp. 26–30, Graphics Gems II.

Leituras adicionais

Warren Jr., Henry S. (2013). Hacker's Delight 2 ed. [S.l.]: Addison Wesley – Pearson Education, Inc. ISBN 978-0-321-84268-8
McKenna, Douglas M. (2019). Hilbert Curves: Outside-In and Inside-Gone. [S.l.]: Mathemaesthetics, Inc. ISBN 978-1-7332188-0-1

Ligações externas

[1] Moon, B.; Jagadish, H.V.; Faloutsos, C.; Saltz, J.H. (2001), «Analysis of the clustering properties of the Hilbert space-filling curve», IEEE Transactions on Knowledge and Data Engineering, 13 (1): 124–141, CiteSeerX 10.1.1.552.6697, doi:10.1109/69.908985 .

[2] «Mapping the whole internet with Hilbert curves». blog.benjojo.co.uk. Consultado em 2 de janeiro de 2021

[3] Spires, Shannon V.; Goldsmith, Steven Y. (1998), Drogoul, Alexis; Tambe, Milind; Fukuda, Toshio, eds., «Exhaustive geographic search with mobile robots along space-filling curves», ISBN 978-3-540-64768-3, Berlin, Heidelberg: Springer Berlin Heidelberg, Collective Robotics, 1456, pp. 1–12, doi:10.1007/bfb0033369, consultado em 14 de agosto de 2023

[4] Sadat, Seyed Abbas; Wawerla, Jens; Vaughan, Richard (2015). Fractal trajectories for online non-uniform aerial coverage. 2015 IEEE International Conference on Robotics and Automation (ICRA). pp. 2971–2976

[5] Thiadmer Riemersma (1 de dezembro de 1998). «A Balanced Dithering Technique». Dr. Dobb's. C/C++ User's Journal

[6] Thiadmer Riemersma (1 de dezembro de 1998). «A Balanced Dithering Technique». Dr. Dobb's. C/C++ User's Journal

[7] Eavis, T.; Cueva, D. (2007). «A Hilbert Space Compression Architecture for Data Warehouse Environments». Data Warehousing and Knowledge Discovery. Col: Lecture Notes in Computer Science. 4654. [S.l.: s.n.] pp. 1–12. ISBN 978-3-540-74552-5. doi:10.1007/978-3-540-74553-2_1

[8] Lemire, Daniel; Kaser, Owen (2011). «Reordering Columns for Smaller Indexes». Information Sciences. 181 (12): 2550–2570. arXiv:0909.1346. doi:10.1016/j.ins.2011.02.002

[9] Hamilton, C. H.; Rau-Chaplin, A. (2007). «Compact Hilbert indices: Space-filling curves for domains with unequal side lengths». Information Processing Letters. 105 (5): 155–163. doi:10.1016/j.ipl.2007.08.034

[10] Alber, J.; Niedermeier, R. (2000). «On multidimensional curves with Hilbert property». Theory of Computing Systems. 33 (4): 295–312. CiteSeerX 10.1.1.7.2039. doi:10.1007/s002240010003

[11] H. J. Haverkort, F. van Walderveen, Four-dimensional Hilbert curves for R-trees, in: Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009, pp. 63–73.

[12] Voorhies, Douglas: Space-Filling Curves and a Measure of Coherence, pp. 26–30, Graphics Gems II.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]