A genetic algorithm to solve a space-filling curve problem

Valentin Owczarek (1) , Patrick Franco (1) , Rémy Mullot (1)

1 L3I - Laboratoire Informatique, Image et Interaction - EA 2118

A space-filling curve (SFC) is an ordering function which creates a bijection between integers I and points X lying in a D-dimensional regular grid. This ordering has the property to conserve the distance, i.e. close points in the space have close indices. This property known as the locality preserving. At this time, the Hilbert curve defined by D. Hilbert [1] in 1891 achieve the best locality preserving level [2]. In various domain, many applications are drawn on the locality preservation properties of space-filling curves. For example, one could concern global optimization, data visualization, image compression and encryption. Recently, G. Nguyen [3] proposed a new algorithm to compute SFCs where the curve at order n = 1 is used to recursively define the bijection between the D-dimensional grid and the indices. This new formulation is able to define any Hilbert like SFC. Using this new definition of SFC, relevant studies have been performed by P. Franco to investigate the influence of the pattern for the locality preserving level of the n order curve. The results proved that it is possible to create comparable or better SFC than the regular Hilbert curve which is considered, in the literature, as the best locality preserving curve. In this paper, Genetic Algorithm (GA) are designed to find high locality preserving paper. We prove the non-optimality of the Hilbert Space Filling Curve, according to the Faloutsos standard criteria.

Domaines: Recherche opérationnelle [math.OC]

Valentin Owczarek, Patrick Franco, Rémy Mullot. A genetic algorithm to solve a space-filling curve problem. SLS2019: International Workshop on Stochastic Local Search Algorithms, Sep 2019, Lille, France. pp.5-6. ⟨hal-02297854⟩