6.3 Space-filling curves (e.g., Hilbert curve, Peano curve)

Space-filling curves are mind-bending mathematical objects that squeeze an infinite line into a finite area. They're like intricate mazes that cover every nook and cranny of a square, leaving no space untouched.

These curves, like the Hilbert and Peano curves, are built through repeated iterations. Each step adds more twists and turns, creating a fractal-like pattern that fills space completely. They're a perfect blend of geometry and infinity.

Space-filling curves: construction and properties

Iterative construction process

Top images from around the web for Iterative construction process

• 

  Category:Sierpinski curves - Wikimedia Commons View original

  Is this image relevant?

• 

  Category:Sierpinski curves - Wikimedia Commons View original

  Is this image relevant?

• 

  Hilbert curve | TikZ example View original

  Is this image relevant?

• 

  Category:Sierpinski curves - Wikimedia Commons View original

  Is this image relevant?

• 

  Category:Sierpinski curves - Wikimedia Commons View original

  Is this image relevant?

1 of 3

Top images from around the web for Iterative construction process

• 

  Category:Sierpinski curves - Wikimedia Commons View original

  Is this image relevant?

• 

  Category:Sierpinski curves - Wikimedia Commons View original

  Is this image relevant?

• 

  Hilbert curve | TikZ example View original

  Is this image relevant?

• 

  Category:Sierpinski curves - Wikimedia Commons View original

  Is this image relevant?

• 

  Category:Sierpinski curves - Wikimedia Commons View original

  Is this image relevant?

1 of 3

• Space-filling curves pass through every point of a unit square (or cube in higher dimensions) filling the entire space
• Construction involves an iterative process adding more detail and complexity to the curve with each iteration
• Iterative process limit results in a curve with infinite length contained within a finite area
• Notable examples include Hilbert curve, Peano curve, Sierpiński curve, and Moore curve

Fractal properties

• Self-similar curves exhibit fractal-like properties with repeating patterns at different scales
• Fractal dimension of 2 in the plane (or 3 in three-dimensional space) despite being one-dimensional objects
• Not differentiable at any point constantly changing direction to fill the space completely

Hilbert curve: hierarchical structure

Construction and iterations

• First described by mathematician David Hilbert in 1891
• Begins with a U-shaped curve following specific rules for each iteration
• Each iteration divides the square into four quadrants with the curve passing through each quadrant exactly once
• Hierarchical structure builds upon previous iterations by replacing each segment with a scaled-down version of the basic U-shape
• Generalizes to higher dimensions creating space-filling curves in three-dimensional space and beyond

Properties and characteristics

• Maintains locality properties points close in one-dimensional space along the curve are also close in two-dimensional space
• Fractal dimension of 2 reflecting its space-filling nature despite being a one-dimensional object
• Preserves spatial relationships between points better than other space-filling curves (Peano curve)
• Exhibits self-similarity at different scales each iteration contains smaller copies of the entire curve

Peano curve: space-filling properties

Construction and iterations

• Introduced by Giuseppe Peano in 1890 first example of a space-filling curve discovered
• Construction involves dividing a square into nine equal sub-squares and connecting their centers in a specific pattern
• Each iteration increases complexity by applying the same pattern to each of the nine sub-squares from the previous iteration
• Variations include Peano-Gosper curve and Wunderlich curve each with unique properties and construction methods

Properties and characteristics

• Exhibits self-similarity each iteration contains scaled-down versions of the entire curve
• Does not preserve locality as strongly as Hilbert curve points close on the curve may not be as close in two-dimensional space
• Fractal dimension of 2 indicating its space-filling nature in the plane
• Fills space more densely than Hilbert curve due to its nine-square division pattern

Applications of space-filling curves: indexing vs data storage

Multidimensional indexing and data storage

• Map multidimensional data to one-dimensional space facilitating efficient data storage and retrieval
• Hilbert curve creates compact file structures for multidimensional databases due to strong locality preservation properties
• Used in geographical information systems (GIS) for mapping two-dimensional spatial data to one-dimensional indices
• Applied in parallel computing for load balancing and data distribution across multiple processors
• Exploited in quad-tree and oct-tree data structures for efficient spatial indexing and searching

Image processing and computer graphics

• Used for image compression creating linear orderings of two-dimensional image data
• Applied in texture generation and mapping for computer graphics applications
• Facilitate efficient storage and retrieval of large image datasets
• Enable hierarchical representation of image data for multi-resolution analysis