American Scientist

OPT ART: From Mathematical Optimization to Visual Design. Robert Bosch. 188 pp. Princeton University Press, 2019. $29.95.

Held at arm’s length, the illustration below is easily recognized as a portrait of the 44th president of the United States. Closer examination reveals that the image is formed from blocks of white dots set against a black background. The dots are the white pips on dominos—specifically, “double nine” dominos, which have from zero to nine dots on each half of a rectangular tile (see detail below, right). A full set of double-nine dominos contains 55 pieces. The portrait of Barack Obama combines 44 such full sets, for a total of 2,420 tiles, arranged to create light and dark patterns that the eye interprets as an image.

Dominos first became a medium for this type of visual expression 40 years ago in the hands of Ken Knowlton, a computer scientist and artist at Bell Laboratories, whose work appeals to those who like a dash of math and algorithms with their artwork. Robert Bosch, the creator of the Obama portrait, takes this nerdish genre to a higher level of refinement. Starting from a black-and-white photograph or other monochrome image, his goal is not just to produce a good likeness but to find the best possible arrangement of the dominos—the configuration that most closely matches the pattern of shadow and light in the original, according to a mathematical measure. His recent book, Opt Art: From Mathematical Optimization to Visual Design, celebrates this idea of optimal or optimized graphic works, along with the computational tools needed to create them.

To build the Obama mosaic, Bosch began with a photograph, using a 55 × 88 grid to divide it into a total of 4,840 square regions. The range of gray levels in the image was compressed to 10 discrete values, labeled from 0 (the darkest) through 9 (the brightest). Then came the tricky part: placing the dominos on pairs of adjacent squares so that the number of pips in each square matched the assigned gray value as closely as possible. As the detail below the mosaic shows, there were many choices to be made, not only in selecting the best tile for each place but also in deciding how it should be oriented. At the end of the process every square needed to be covered, with no gaps or overlaps, and every domino in the 44 sets had to have a home somewhere in the picture.

How can you find the best possible arrangement of 2,420 double-nine dominos? Trying all possible configurations is not a feasible approach. Even working with just a single set of dominos, and ignoring some messy details of geometry and orientation, there are more than 10⁷³ ways of placing the 55 tiles. To break through this combinatorial bottleneck, Bosch turned to methods known as linear optimization, or linear programming. “Linear” signifies that the solution space is bounded by straight lines or flat planes; no curves are allowed.

The problem-solving tools of linear optimization come out of a milieu far from the world of the arts. Historically, they are closely associated with business and economics, logistics, management, and military planning. An airline might use linear programming to match up aircraft, flight segments, and crew members. A chemical plant might use it to adjust its operations to yield the most profitable mix of products. Yet art, too, is an exercise in problem-solving and constraint satisfaction. Furthermore, constraints in the arts can be inspirations rather than obstacles. Bosch cites the example of Georges Seurat’s pointillist painting A Sunday Afternoon on the Island of La Grande Jatte. “Seurat set himself the task of producing the best possible depiction of what he saw on the riverbank, subject to two highly restrictive, self-imposed constraints: he had to keep his colors separate, and he could only apply paint to the canvas with tiny, precise, dot-like brush strokes.” It sounds a little like painting with dominos.

Bosch is a professor of mathematics at Oberlin College, where he teaches optimization (among other subjects). In Opt Art he gives a brief explanation of the underlying mathematics, based on a cute question: What can you build with a fixed supply of Lego bricks? He then introduces optimization procedures for some comparatively simple mosaics, in which each tile covers a single square, before turning to the more challenging domino tilings.

The narrative later turns to a quite different kind of data-optimizing artwork: connect-the-dots drawings in which a scene is rendered by a continuous closed path that can be drawn without lifting the pen from the paper. The first step is to create the set of dots to be connected—typically several thousand of them—using a stippling technique in which a higher local density of dots will produce a darker region in the finished drawing. Drawing the path from dot to dot to dot and eventually back to the starting point is where optimization enters the problem. The objective is to find the shortest possible route for such a tour. This is one of the famous hard problems of computer science, known as the traveling salesman problem, which is not believed to have an efficient solution; nevertheless, linear optimization algorithms can find a good tour for problems of the size considered in Opt Art. With further work and ingenuity, it is often possible to prove that a tour is not only good but optimal. The illustration below shows four point sets on top and four corresponding optimal tours beneath them for a detail from Michelangelo’s Creation of Adam.

I note in passing that the stippled versions of these drawings are actually more appealing to my eye than those with the traced paths. The algorithms for finding a good stipple pattern are also interesting. But in the stippling process there is no criterion for defining optimality; the choice of pattern is made by a more conventional kind of aesthetic judgment, based on what pleases the eye.

Bosch goes on to present a gallery of other graphic fantasies generated by various optimizing procedures, applying them to knots, knight’s tours on the chessboard, labyrinths, and tilings that obey additional constraints. One of my favorites is the idea of a “still-life tiling,” based on John Horton Conway’s Game of Life. The basic elements of the tableau are tiny black or white squares, called cells, arranged in a large grid. What sets the system apart from other tilings is that the cells interact with one another, changing their own color in response to the configuration of the surrounding cells. Bosch sets up patterns that are stable for a while and then slowly disintegrate as a result of these interactions, like a sand painting swept away by the wind.

Opt Art serves as an inviting introduction to a curious corner where art and mathematics intersect. Bosch projects equal enthusiasm for both. The artwork is not just an ornament meant to attract a broader readership, and the math is not just a tool for producing pictures. For Bosch it’s clear they both hold deep intrinsic interest, and he communicates this to the reader.

My one major disappointment with the book is that readers who want to experiment with these ideas for themselves may find too little guidance in it to make a successful start. Although Bosch supplies the key mathematical background, the practical details of turning basic principles into working computer programs are rather intimidating. Compounding this problem, Bosch does most of his work with the proprietary software package Gurobi Optimizer, which is available free to those with an academic affiliation but is probably beyond the means of other casual users. Suggesting a few alternatives would have been helpful.