direita|miniaturadaimagem|Primeiras 6 iterações da 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 -ésima curva é , i.e., o comprimento cresce exponencialmente com , mesmo que cada curva esteja contida num quadrado de área .

Imagens

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.. 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. A propriedade de localidade da curva de Hilbert também foi usada para projetar algoritmos para explorar regiões com robôs móveis.

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. 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 (veja a árvore R de Hilbert). Elas também foram usadas para ajudar a comprimir data warehouses.

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. Além disso, existem várias generalizações possíveis das curvas de Hilbert para dimensões superiores.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.

Representação como um sistema de Lindenmayer A Curva de Hilbert pode ser expressa por um sistema de reescrita (L-sistema). miniaturadaimagem|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"Voorhies, Douglas: Space-Filling Curves and a Measure of Coherence, pp. 26–30, Graphics Gems II. 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.

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

Leituras adicionais

Ligações externas

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 Iterative algorithm for drawing Hilbert curve in JavaScript Algorithm 781: generating Hilbert's space-filling curve by recursion (ACM Digital Library) Categoria:David Hilbert Categoria:Fractais