September 24, 2020

Constructing Domino Portraits

In 1840, the Danish artist Christian Albrecht Jensen (1792–1870) was commissioned to paint a portrait of the renowned mathematician Carl Friedrich Gauss (1777–1855). This portrait, showing Gauss at the venerable age of 63, went on display at the Pulkovo Observatory in St. Petersburg, Russia, where it remains to this day.

That painting of Gauss has been copied many times over the years, with variants of the portrait even appearing on bank notes and postage stamps. One recent rendition of the Gauss portrait was constructed entirely from 48 complete sets of double-nine dominoes.


A portrait of Carl Friedrich Gauss (above) constructed from 48 complete sets of dominoes (detail, below). Courtesy of Robert Bosch.


The work of mathematician Robert Bosch, this remarkable creation and others like it represented the successful application of a novel algorithm for approximating target images as arrays of dominoes.

To create a domino portrait, Bosch started with an image—a picture of Gauss, Abraham Lincoln, Marilyn Monroe, John Lennon, or some other figure—and a certain number of complete sets of dominoes. His goal was to position the dominoes in such a way that, when seen from a distance, the assemblage looked like the target image.

What made this task especially challenging was the self-imposed requirement of using complete sets. Hence, when Bosch worked with 48 sets, he used precisely 48 blank dominoes, 48 dominoes that have a blank square and a square with one dot, and so on. To make this work, the process required delicate compromises on the placement of constituent dominoes.

To find optimal positions for the dominoes, Bosch applied a mathematical technique known as integer programming. Long used in operations research, integer programming has aided schedule construction, route selection, and a variety of other large-scale planning tasks.

Bosch's computer program started by dividing the target image into an array of squares. Some squares were completely white, others were completely black, and the rest were various shades of gray. White squares were assigned the value 9, black squares had the value 0, and gray squares were given intermediate values.


A domino is made up of two squares. A complete set consists of 55 dominoes—10 that are doubles and 45 that are not doubles. Each double has two possible orientations (horizontal or vertical), and each nondouble has four possible orientations. Clearly, double-blank dominoes would most likely go where the grayscale value is 0, and double-nine dominoes would most likely go where the grayscale value is 9.

Using integer programming, Bosch's software determined the optimal placement and orientation of each of the available dominoes. In effect, it selected the arrangement that most closely matched the numbers that described the original image. Choosing a larger number of sets of dominoes enabled the rendering of a more accurate approximation of the original image.


A portion of an image was divided into squares (above) with grayscale values between 0 and 9 (below).


Bosch's computer program then worked out the arrangement of dominoes (below) that gave the best possible match with the image's grayscale values. Courtesy of Robert Bosch.


Bosch has created more than 100 domino portraits (examples). See also his book Opt Art: From Mathematical Optimization to Visual Design (Princeton University Press, 2019).


A classroom project involving first- and second-graders produced a domino portrait of Martin Luther King Jr. Courtesy of Robert Bosch.

Originally posted April 14, 2003

See also "Embrace" and "Moebius Meander."

No comments: