An intelligent approach for curve filling

1 Introduction

There are several results in the mathematical literature allowing the calculation of the box dimension of subsets of ℝ d by means of the box dimension of 1-dimensional subsets. Among them, we can quote Theorem 4.1 in [9], based on the existence of a δ-uniform curve from [0, 1] to the d-cube as well as Theorem 1 in [13], which lies on the existence of a quasi-inverse function from [0, 1] ^d to the closed unit interval for some space-filling curves including the Peano, Hilbert, and Sierpinśki ones.

Recently, a result in this line has been provided in the context of fractal structures, a kind of uniform spaces (c.f. Definition 2.1). In this case, such a theorem depends on a function α which allows linking the elements of the natural fractal structure on [0, 1] ^d (c.f. Definition 2.2), Δ, with the elements of a certain fractal structure defined on [0, 1] under the assumption that Δ = α (Γ) (c.f. either Theorem 2.4 or Corollary 2.5). Given this, along this paper we shall highlight an intelligent procedure to properly construct such a curve α, see [6] for more details.

As such, the structure of this work remains as follows. Section 2 contains the mathematical framework Theorem 3.3 is based on. The main result in this paper appears in Section 3. Finally, Section 4 illustrates some applications of Theorem 2.4 to curve filling.

2 Mathematical framework

Firstly, recall that a covering of a set X is a collection of subsets, Γ, such that X = ∪ {A : A ∈ Γ}. Next, we provide the powerful concept of a fractal structure.

Definition 2.1. (c.f., e.g., Definition 2.1 in [8]) Let Γ = { Γ n : n ∈ ℕ } be a countable family of coverings of X. We shall understand that Γ is a fractal structure provided that the two following statements hold:

for each A ∈ Γ_n+1, there exists B ∈ Γ _n such that A ⊆ B.

If Γ is a fractal structure on X, we say that the pair (X, ef) is a generalized-fractal space (GF-space, for short).

Below, the natural fractal structure on each Euclidean space ℝ d , which stands as a particular case from Definition 3.1 in [7], is described.

Definition 2.2. The natural fractal structure on the ℝ 2 is the countable family of coverings, Δ = { Δ n : n ∈ ℕ } , with levels given by Δ n = { [ k 1 2 n , 1 + k 1 2 n ] × … × [ k d 2 n , 1 + k d 2 n ] : k 1 , … , k d ∈ ℤ } .

It is worth pointing out that the natural fractal structure just provided in Definition 2.2 can be induced on the d-cube [0, 1] ^d as follows.

Remark 2.3. The natural fractal structure on [0, 1] ^d is the family of coverings Δ = { Δ n : n ∈ ℕ } whose levels are defined as Δ n = { [ k 1 2 n , 1 + k 1 2 n ] × … × [ k d 2 n , 1 + k d 2 n ] : k 1 , … , k d = 0 , 1 , … , 2 n - 1 } for all n ∈ ℕ (c.f. Fig. 1).

OPEN IN VIEWER

Fig. 1

The figure above illustrates the first two levels in the natural fractal structure on [0, 1] × [0, 1]. Observe that the first level consists of four squares with sides equal to, Γ₂ contains 4² squares with sides equal to 1 2 2 , and in general, level n consists of 4 ⁿ squares with sides equal to 1 2 n .

Interestingly, the following approach becomes especially appropriate to deal with the effective calculation of the box dimension of Euclidean subsets, since it allows applying the already existing procedures to calculate the box dimension of 1-dimensional subsets.

Theorem 2.4.(c.f. Theorem 2.8 in [5]) Let Δ be the natural fractal structure on [0, 1] ^d , and assume that [0, 1] is endowed with the fractal structure Γ whose levels are Γ n = { [ k 2 nd , 1 + k 2 nd ] : k = 0 , 1 , … , 2 nd - 1 } . Moreover, let F be a subset of [0, 1] ^d, and α : [0, 1] → [0, 1] ^d a function such that Δ = α (Γ). Then the (lower/upper) box dimension of F equals the (lower/upper) box dimension of α^-1 (F) ⊆ [0, 1] up to a factor, namely, the embedding dimension, d. In particular, if dim_B(F) exists, then dim_B(α^-1 (F)) also exists (and reciprocally), and it holds thatdim B ( F ) = d ⋅ dim B ( α − 1 ( F ) )(1)

Alternatively, a more operational version of previous Theorem 2.4 can be stated in the following terms.

Corollary 2.5.(c.f. both Theorem 4.1 and Remark 4.4 in [5]) Let Δ be the natural fractal structure on [0, 1] ^d , and assume that [0, 1] is endowed with the fractal structure Γ with levels Γ n = { [ k 2 nd , 1 + k 2 nd ] : k = 0 , 1 , … , 2 nd - 1 } for all n ∈ ℕ . In addition, let F be a subset of [0, 1] ^d , and α : [0, 1] → [0, 1] ^d a function such that Δ = α (Γ). Then the lower and upper box dimensions of F can be calculated throughout the following expressions, respectively: dim ¯ B ( F ) = d · lim ¯ δ → 0 log N δ ( α − 1 ( F ) ) − log δ . dim ¯ B ( F ) = d · lim ¯ δ → 0 log N δ ( α − 1 ( F ) ) − log δ .

In particular, if the box dimension of F exists, then dim B ( F ) = d · lim δ → 0 log N δ ( α − 1 ( F ) ) − log δ ,(2) where N δ ( α - 1 ( F ) ) is the number of δ-cubes that intersect α^-1 (F) ⊆ [0, 1], and a δ-cube in ℝ d is a set of the form [ δ k 1 , δ ( 1 + k 1 ) ] × … × [ δ k d , δ ( 1 + k d ) ] : k 1 , … , k d ∈ ℤ .

As such, the previous results involve a fractal structure Δ on [0, 1] ^d (i.e., the natural one), another fractal structure Γ on the closed unit interval, and a function α : [0, 1] → [0, 1] ^d such that Δ = α (Γ) to guarantee both Equations (1) and (2). Though there are no restrictions regarding that the α apart from the condition Δ = α (Γ), along upcoming Section 3 we shall highlight an intelligent construction based on a sequence of stages to properly apply Theorem 2.4 (resp. Corollary 2.5) to calculate the box dimension in higher dimensional spaces.

In this section, we state the key result in this paper. First, we would like to mention that the concept of a starbase fractal structure plays a key role to construct that function α.

Definition 3.1. ([1], Section 2.2) Let Γ be a fractal structure on X. We say that Γ is starbase if St ( x , Γ n ) = { St ( x , Γ n ) : n ∈ ℕ } is a neighborhood base of x for all x ∈ X, where St (x, Γ _n ) = ∪ {A ∈ Γ _n : x ∈ A}.

A sequence { A n : n ∈ ℕ } is said to be decreasing provided that A_n+1 ⊆ A _n for all n ∈ ℕ .

Definition 3.2. ([2], Definition 3.1.1) Let Γ = { Γ n : n ∈ ℕ } be a fractal structure on X. We say that Γ is Cantor complete if for each decreasing sequence { A n : n ∈ ℕ } with A _n ∈ Γ _n , it holds that ∩ n ∈ ℕ A n ≠ ∅ .

Following the concepts above, we have the following

Theorem 3.3. ([4], Theorem 3.6) Let Γ = { Γ n : n ∈ ℕ } be a starbase fractal structure on a metric space X, Δ = { Δ n : n ∈ ℕ } a Cantor complete starbase fractal structure on a complete metric space Y, and { α n : Γ n → Δ n : n ∈ ℕ } a collection of functions. Consider the following list of statements:

if A∩ B ≠ ∅ with A, B ∈ Γ _n for some n ∈ ℕ , then α _n (A)∩ α _n (B) ≠ ∅.

The two following hold for all A ∈ Γ _n and n ∈ ℕ :

If both conditions (i) and (ii) stand, there exists a unique continuous function α : X → Y such that α (A) ⊆ α _n (A).

Proof. Firstly, we shall define the function α : X → Y. For each x ∈ X, there exists a decreasing sequence { A n : n ∈ ℕ } such that A _n ∈ Γ _n for all n ∈ ℕ with x ∈ ∩ n ∈ ℕ A n . Thus, { α n ( A n ) : n ∈ ℕ } is also decreasing with α _n (A _n ) ∈ Δ _n for all n ∈ ℕ . Moreover, it holds that ∩ _n α _n (A _n ) is a single point, since Δ is starbase and Cantor complete. Therefore, we shall define α ( x ) = ∩ n ∈ ℕ α n ( A n ) . As such, we affirm that α is well-defined. In fact, let x ∈ X and assume that there exist a pair of decreasing sequences of subsets of X, { A n : n ∈ ℕ } and { A n ′ : n ∈ ℕ } , such that A n , A n ′ ∈ Γ n for all n ∈ ℕ with x ∈ ∩ n ∈ ℕ A n and x ∈ ∩ n ∈ ℕ A n ′ , as well. Suppose, in addition, that ∩ n ∈ ℕ α n ( A n ) = { y } and ∩ n ∈ ℕ α n ( A n ′ ) = { z } with y ≠ z. Then there exists a natural number n such that St (y, Δ _n )∩ St (z, Δ _n ) = ∅, since Δ is starbase. Hence, α n ( A n ) ∩ α n ( A n ′ ) = ∅ . However, on the other hand, we have that x ∈ A n ∩ A n ′ for all n ∈ ℕ . Thus, α n ( A n ) ∩ α n ( A n ′ ) ≠ ∅ by condition (i), a contradiction. Accordingly, y = z.

Under both conditions (i) and (ii), the following statements hold:

α (A) ⊆ α _n (A) for all A ∈ Γ _n and n ∈ ℕ . This is clear from the definition of α.

4 Applications to curve filling

The main goal in this section is to show how Theorem 3.3 allows the construction of space-filling curves with a different nature. As such, while Subsection 4.1 deals with the definition of the Hilbert’s curve by levels, Subsection 4.2 tackles with the construction of a curve filling an attractor. These functions allow defining appropriate connections among the elements in each level of both fractal structures, Γ and gf, and hence, enable the application of Theorem 2.4 (resp., Corollary 2.5) to calculate the box dimension of subsets of ℝ d by means of the box dimension of 1-dimensional subsets.

4.1 A curve filling the Hilbert’s curve

First, let us show how the classical Hilbert’s plane-filling curve (c.f. [10]) can be iteratively described by levels.

Example 4.1. (c.f. Example 1 in [4]) Let (Y, Δ) be a GF-space with Y = [0, 1] × [0, 1] and Δ being the natural fractal structure on [0, 1] × [0, 1] as a Euclidean subset, i.e., Δ = { Δ n : n ∈ ℕ } , where Δ n = { [ k 1 2 n , 1 + k 1 2 n ] × [ k 2 2 n , 1 + k 2 2 n ] : k 1 , k 2 = 0 , 1 , … , 2 n - 1 } for each n ∈ ℕ . In addition, let (X, ef) be another GF-space where X = [0, 1] and = { Γ n : n ∈ ℕ } with Γ n = { [ k 2 2 n , 1 + k 2 2 n ] : k = 0 , 1 , … , 2 2 n - 1 } . It is worth pointing out that each level n of Γ (resp., of Δ) contains 2²ⁿ elements. Next, we explain how to construct a function α : X → Y such that Δ = α (Γ). To deal with, we shall define the image of each element in level n of Γ through a function α _n : Γ _n → Δ _n . For instance, let α ( [ 0 , 1 4 ] ) = [ 0 , 1 2 ] 2 , α ( [ 1 4 , 1 2 ] ) = [ 1 2 , 1 ] × [ 0 , 1 2 ] , α ( [ 1 2 , 3 4 ] ) = [ 1 2 , 1 ] 2 , and α ( [ 3 4 , 1 ] ) = [ 0 , 1 2 ] × [ 1 2 , 1 ] , as well (c.f. Fig. 2). Thus, the whole level Δ₁ = α (Γ₁) = {α (A) : A ∈ Γ₁} has been defined. It is worth mentioning that this approach provides additional information regarding α as deeper levels of both Γ and Δ are reached via α _n under the two following conditions (c.f. Theorem 3.3):

If A∩ B ≠ ∅ with A, B ∈ Γ _n for some n ∈ ℕ , then α _n (A)∩ α _n (B) ≠ ∅.

If A ⊆ B with A ∈ Γ_n+1 and B ∈ Γ _n for some n ∈ ℕ , then α_n+1 (A) ⊆ α _n (B).

For instance, if A ∈ Γ _n , then we can calculate its image via α _n , α _n (A). Going beyond, let B ∈ Γ_n+1 be so that B ⊆ A. Then α_n+1 (B) ⊆ α _n (A) refines the definition of α _n (A), and so on. This allows us to think of the Hilbert’s curve as the limit of the maps α _n (c.f. Fig. 3). This example illustrates how Theorem 3.3 allows the construction of (continuous) functions and in particular, space-filling curves.

OPEN IN VIEWER

Fig. 2

The two plots above arrange how each element in level n of Γ is sent to some element in level n of Δ via α _n for n = 2, 3.

OPEN IN VIEWER

Fig. 3

First three levels in the construction of the Hilbert’s curve according to Theorem 3.3.

4.2 A curve filling the Sierpinśki gasket

Let k ≥ 2. By an iterated function system, we shall understand a finite collection of similitudes on ℝ d , ℱ = { f 1 , … , f k } , where each self-map f i : ℝ d → ℝ d satisfies the following identity: d ( f i ( x ) , f i ( y ) ) = c i · d ( x , y ) , for all x , y ∈ ℝ d , where d denotes the Euclidean distante and c _i ∈ (0, 1) is the similarity ratio associated with each f _i . Under the previous assumptions, there always exists a unique (nonempty) compact subset K ⊆ ℝ d such that K = ⋃ { f i ( K ) : i = 1 , … , k } .

The previous equality is usually known as Hutchinson’s equation (c.f. [11]) and K is named the attractor (also the self-similar set) generated by F .

Next, we define the natural fractal structure that each attractor can be always endowed with.

Definition 4.2. (c.f. [3], Definition 4.4) Let F be an IFS whose attractor is K . The natural fractal structure on K as a self-similar set is given by the countable family of coverings Γ = { Γ n : n ∈ ℕ } , where Γ 1 = { f i ( K ) : i = 1 , … , k } , and Γ_n+1 = {f _i (A) : A ∈ Γ _n , i = 1, …, k} for each n ∈ ℕ .

It is worth mentioning that such a fractal structure is starbase (c.f. [3, Theorem 4.7]).

Interestingly, it holds that Theorem 3.3 also allows the construction of maps filling a whole attractor. Next, we shall illustrate it by generating a curve that crosses (once) each element of the natural fractal structure which the Sierpiński gasket (c.f. [12]) can be endowed with as a self-similar set (c.f. Definition 4.2).

Example 4.3. (c.f. Example 4 in [4]) Let I = [0, 1] endowed with the fractal structure Γ = { Γ n : n ∈ ℕ } with levels given by Γ n = { [ k 3 n , 1 + k 3 n ] : k = 0 , 1 , … , 3 n - 1 } for each n ∈ ℕ . In addition, let K be the Sierpiński triangle contained in the equilateral triangle with set of vertices given by { ( 0 , 0 ) , ( 1 2 , 1 ) , ( 1 , 0 ) } . Let K be endowed with its natural fractal structure as a self-similar set, namely, let Δ = { Δ n : n ∈ ℕ } with Δ 1 = { f i ( K ) : i ∈ I } and Δ_n+1 = {f _i (A) : A ∈ Δ _n , i ∈ I} for all n ∈ ℕ , where I = {1, 2, 3} and the three similitudes f i : ℝ 2 → ℝ 2 leading to K are defined as follows: f i ( x , y ) = { ( x 2 , y 2 ) if i = 1 f 1 ( x , y ) + ( 1 2 , 0 ) if i = 2 f 1 ( x , y ) + ( 1 4 , 1 2 ) if i = 3 for all ( x , y ) ∈ ℝ 2 . Thus, the Sierpiński gasket is fully determined as the unique non-empty compact subset K satisfying the Hutchinson’s equation K = ∪ i ∈ I f i ( K ) . Observe that each piece f i ( K ) is a self-similar copy of the whole Sierpiński triangle. Similarly to Example 4.1, next we construct a map γ such that Δ = γ (Γ). Let n ∈ ℕ . Next, we shall provide further refinements of γ by defining the image of each element A ∈ Γ _n via γ _n : Γ _n → Δ _n . Thus, we can define γ ( [ 0 , 1 3 ] ) as the equilateral triangle whose set of vertices is { ( 0 , 0 ) , ( 1 2 , 0 ) , ( 1 4 , 1 2 ) } , γ ( [ 1 3 , 2 3 ] ) , as the equilateral triangle with set of vertices { ( 1 2 , 0 ) , ( 3 4 , 1 2 ) , ( 1 , 0 ) } , and γ ( [ 2 3 , 1 ] ) is the equilateral triangle with set of vertices { ( 1 4 , 1 2 ) , ( 1 2 , 1 ) , ( 3 4 , 1 2 ) } , as well. This allows to define Δ₁ = γ (Γ₁) = {γ (A) : A ∈ Γ₁}. Similarly, the next levels of Δ can be defined. Fig. 4 illustrates such a construction. It is worth mentioning that the polygonal line shows the path followed to cross (once) all the elements in each level of the natural fractal structure in K . Thus, γ = K with γ being equal to the limit of the maps γ _n as n→ ∞.

OPEN IN VIEWER

Fig. 4

First two levels in the construction of a curve filling the whole Sierpiński gasket.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.