Robert Bosch is a mathematician who has produced computer generated art that can be found on his website and that he also presented at the Bridges mathart conferences. The pleasing optical effect of his graphical art is generated by solving some constrained optimization problem. The objective function is often simple, but the challenge is to design and formulate appropriate constraints.

One possible example is the construction of mosaics to represent a given image in a recognizable way where the elementary tiles of the mosaic are used like dots in halftone images or in pointillist paintings. Given is a restricted set of (small) tiles to choose from and some (large) picture. Put a relatively fine square grid over the picture and replace each square of the grid (let's call them pixels) with a tile from your set whose greyscale approximates the original greyscale of that square. The first example in this book is using flexible Truchet tiles to build the picture. A Truchet tile is a square tile with a diagonal dividing the square into a black and a white triangle. By introducing a parameter to move the midpoint of the diagonal along the other diagonal it is possible to generate tiles whose average greyscale ranges from 75 percent black to 75 percent white. Finding the optimal parameter for each tile to match the greyscale of the corresponding square pixel of the image is a large constrained optimization problem. Note that a Truchet tile has four rotationally symmetric siblings. This can be taken into account by defining larger composed tiles in which the unit tiles have a prescribed orientation. Obviously what is done for squares can be extended to any other shape of tile with rotational symmetry that fills the plane. Representing coloured instead of greyscale images can be an extra complication.

As an example of a constrained optimization problem some elementary introduction to the simplex method is given and it is illustrated how such a problem can be solved. It is not necessary to understand all the mathematics since computations are done by optimization software. One only needs to know how to feed the problem to the software. Most applications in the book use the Gurobi optimization software, except for the travelling salesman problems, for which the Concorde TSP package is used. Once the software is available, the previous idea of Truchet tiles matching the greyscale of a picture can be applied by using any dictionary of tiles with different average degrees of darkness. It becomes more challenging when one uses domino tiles, which for this purpose are double nines, that means that the number of dots on half the domino is not between zero and six as usual, but they have between zero and nine dots. Thus there are 55 domino tiles in a complete set ranging from double blank to double nine without repetition. The extra complications with respect to the previous problems are that these tiles are rectangular, and one has to decide how they are oriented to cover two square pixels of the original image. Moreover one can restrict the available dominoes to be only a finite number of complete domino sets that should be used completely. Thus there is only a finite number of copies of each tile. Two methods are explained to solve this problem.

Another goldmine to dig from is the travelling salesman problem (TSP) and all its applications. First it is explained what the optimization problem is and how to solve it approximately and how to avoid disjunct subtours. One should first select random points that are closer together where the image is dark and sparser where the image is light. That is called stippling. Again there are algorithms to solve this stippling problem and they will generate a set of points. This is based on MacQueen's unsupervised learning algorithm to detect clusters. Once the dots are chosen, they need to be connected by one and only one TSP tour, hence producing a piecewise linear Jordan curve that connects all the points in one non-intersecting tour that is of minimal length, at least approximately. Plotting this path with a black line, will show a graph that from a distance will again give a greyscale representation of the original image. It you do not like the piecewise linear curve, it is of course possible to modify the path slightly to turn it into a smooth curve. On the other hand, one could plot a white ribbon on a black background, weaving into a knot like on some Celtic or Arabic graphics. After stippling and finding the TSP contour using extra constraints that prevent points on the ribbon and the contour to "cut" the ribbon where it is not allowed, we are left with the ribbon as blank areas. Depending on symmetry conditions and the imposed constraints it is quite remarkable to detect what is the inside and what is the outside of the Jordan curve that represents the route of the salesman. Some parts of the ribbon are inside while others are outside, which is counter intuitive since from a distance the ribbon looks like in one piece.

Other abstract designs can be obtained by visualizing the knight's tour on a chess board. Another challenging problem is to design a nontrivial maze in such a way that within the outer boundary of the maze, all the squares should be visited exactly once to reach the center. The fine-touch is to design it in such a way that it shows some pleasing pattern. Under the title "Mosaics with side constraints" we find several other variations on the previous techniques that obey some extra restrictions to make the problem more challenging. A very nice idea is based on Conway's game of life. Also this game of life is played on a square grid where every square in the grid represents a cell. The game is a discrete dynamical system in the sense that a cell will live (a dot is present) or die (no dot) depending on some simple rules like the number of its neighbours that are alive. One may collect a number of cells in a larger composite tile that remains stationary under these dynamics and, depending on the number of living cells (dots) it will represent a greyscale tile, which can be used in the previous way to form a mosaic. However, more challenging is to generate composite tiles with cells that alternate between two states, but that do not interact with neighbours. Then one can obtain a dynamic image with a blinking effect.

It is clear that there are many ways to apply the idea of using optimization problems with carefully designed constraints to generate some nice pictures like Robert Bosch illustrates here. I love the book. If you want to start designing yourself, you will find it is far more challenging and probably far more addicting than any game that has been designed for you.