A basic logo design combined with some genetically generated textures.
Spent a couple of hours this evening knocking out a quick TSP solver (greedily chooses shortest edges and then applies 2-opt). Solving for 500 cities requires about half a second. Visual inspection: looks okay. NEOS gives an optimal length of 1632 (not 568 as I first thought in my confusion), whereas this one has a length of 1800 (about 10% longer).
Here’s an interesting I’ve stumbled onto…
I have a set of 2^n distinct colours. I want to generate a map from the integers [0, 2^n) onto this set such that for ‘similar’ colours, the hamming distance between the binary representation of their pre-images in the map is ‘small’.
This isn’t an airtight definition of the problem because I don’t define ‘similar’ or ‘small’. But the intention is that the likelihood that two colours are confused by an observer should be strongly correlated with the number of like-bits in their binary keys.
Here’s a concrete example to make things clearer:
Here’s our set of 4 colours:
Intuitively this looks like an okay solution:
Red and Yellow each differ from Orange by just one binary digit, as do Cyan and Yellow. Less good is the fact that Red and Cyan only differ by one binary digit too even though they are complementary colours. But with such a small number of colours, it’s inevitable that the relationship will be very approximate.
I think that the requirement that every binary representation in [0,2^n) is used is what makes this problem particularly difficult since it seems inevitable to me that in most cases, some ‘bad’ allocations will need to be made - the problem requires global optimization.
I chose to assume that colour similarity was measured by closeness in the RGB colour space treated as a vector space with the euclidean norm. This seems like a practical option when considering algorithms, though I would probably scale the component values in proportion to their luminance contribution. This would have the effect, for example, of making colours that only differ in their blue component ‘more similar’ than if they only differed in their green component say.
How can the creation of the colour map be systemized to produce a close relationship between the keys and the colours?
My thoughts immediately turned to using planes: n planes could partition the colours so that there was exactly one colour in each hull (binary digits allocated according to which side of the planes a point rests); it’s obvious though that there’s no guarantee that such a partitioning will exist.
My second thought was to cluster the colours into two sets and to do this recursively (binary digits allocated according to the clustering); this approach doesn’t look promising either since each cluster would need to be the same size, and the algorithm would not synchronize the binary representations strongly anyway.
So, a couple of minutes in, my final thought was to generate a shortest tour of the colours and then walk it, allocating map keys using a gray code. I may try implementing this approach; it’s the most promising idea I’ve had.
If anyone has a better suggestion I’d be interested to hear it.
