Curva de Hilbert

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 $n$-ésima curva é $2^n-\frac{1}{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. 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.

Representação como um sistema de Lindenmayer

A Curva de Hilbert pode ser expressa por um sistema de reescrita (L-sistema). Ficheiro:Hilbert Curve - 6.webm

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" 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.Predefinição: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

Leituras adicionais

• Predefinição:Citar livro
• Predefinição:Citar livro

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)