Up and Down the Shortest Tree

This image is the result of progressively matching pixels with colours, by running two equivalent and parallel walks, in the 2D image space and 3D colour spectrum.

The walks are constructed by moving back and forth along all the branches of a pre-constructed tree, turning that tree into a Hamiltonian cycle.

To construct the tree in the 2D image space, a grid is formed of square cells that contain 4 pixels each. A root cell is selected, and from there horizontal and/or vertical moves are recursively applied to branch out in any direction, reaching all other cells.

The tree is constructed as a shortest-path tree using the Dijkstra's algorithm, while also choosing at random among any equivalent possibilities.

Once the tree is constructed, a mini-tour is created within the root cell. The mini-tour goes from corner to corner, e.g. top/left to top/right to bottom/right to bottom/left.

Starting from the root cell, all other cells in the tree are then revisited, expanding the tour at each step. The leg in the current cell that is adjacent to the new cell is replaced with a U path in the new cell. By the end of this process the tour has become a Hamiltonian cycle.

An equivalent approach is adopted for the 3D colour space. In this case a grid is formed with cells that are cubes composed of 8 colours. There can be in this case up to three legs in the current cube that are adjacent to the new cube. One of the legs is replaced with a path that visits all the colours in the new cube. Both legs and paths need to be appropriately chosen to avoid ending up with legless surfaces.

This particular image is started by placing a black root at its bottom left corner.

From the root a horizontal branch and a vertical branch form, whose outer side is black-ish and from whose inner side other branches depart, heading at about 45 degrees towards the other side of the image.

Image Licence: Public Domain (CC0).