February 2025
DIMACS is soon to have its first art installation. “Domino Fred” is a mosaic portrait of DIMACS Director Emeritus Fred Roberts created with 23 sets of double-nine dominos. Domino Fred is like many things coming out of DIMACS—it is an application of discrete mathematics, it is connected with a DIMACS program, and it is the result of a collaborative effort to construct a solution. Here, we recount the making of Domino Fred in words, pictures and a time-lapse video!
Domino Mosaics
Domino art came to DIMACS when Bob Bosch, a professor at Oberlin College, lectured in the 2022 Reconnect Workshop on Optimization. Reconnect is a long-running summer workshop series designed to equip faculty teaching undergraduates with topics and materials to engage and inspire their students. Bosch described using optimization techniques to generate art. This included art with string based on chords of a circle (shown in picture), continuous-line drawings based on tours of the traveling salesman problem, and mosaics made from dominos. The latter two are described in Bosch’s fun and readable book, Opt Art. (Also check out his Domino Artwork website.)
A domino mosaic is the solution of a domino mosaic design problem. Given a grayscale image and the number of sets of dominos to use, the goal is to find an arrangement of the dominos to most closely resemble the target image. The resemblance is achieved by matching as closely as possible the brightness of the image with the brightness afforded by the dots on the dominos. To formulate the associated optimization problem, the grayscale image is sized to fit an aspect ratio that is achievable with the given number of dominos and then segmented into square blocks corresponding to one side of a domino or one pixel. A brightness value is computed for each block and scaled to fall between 0 and 9 (to mirror the range of values on the dominos). The dominos are placed to cover the blocks of the original image to minimize the sum of squared errors in brightness, while satisfying constraints that assure that each block is covered by exactly one domino and each domino is used. The result is an integer linear program that is easily solved by available optimization solvers (such as Gurobi).
Lucky for us, NEOS (Network-Enabled Optimization System) has a domino mosaic solver that does all of this for you! Just upload an image, specify whether you want a low, medium, or high resolution, and wait to receive a link to the finished mosaic in email. That’s exactly what we did. Below are: 1) the image we submitted to NEOS; 2) the lowest resolution mosaic based on 23 sets of dominos (this is Domino Fred); and 3) the highest resolution mosaic based on 207 sets.
Using more sets of dominos produces a higher resolution mosaic as well as a larger and more difficult (but still easily solvable) optimization problem. To make this more precise, each set of double-nine dominoes has 55 pieces, each with two sides, so 23 sets creates a 2530-pixel image while 207 sets creates one of 22,770 pixels. Domino Fred’s 2530 pixels are arranged in a rectangle that is 46 by 55 pixels.
Domino Fred
Now let’s fast-forward to 2024 when DIMACS was planning an event to honor Fred Roberts. The DIMACS Tribute to the Many Facets of Fred Roberts—aka FredFest—celebrated Fred’s many contributions to both research and education in fields ranging from discrete mathematics to mathematical biology, sustainability, homeland security, and the social sciences. The organizers of the event sought to reflect Fred’s many dimensions through the breadth of presentations contained in the event’s program as well as a variety of depictions of Fred displayed throughout the venue. Among these depictions were FredNet (a network rendering of Fred’s coauthors), FredClouds (word clouds generated from Fred's paper titles and words describing Fred), and of course, Domino Fred was on display.
The displays actually included two renderings of Domino Fred—one constructed from black dominos with white dots and the other constructed from white dominos with black dots. DIMACS director David Pennock announced plans to construct one of the two versions with real dominos and asked FredFest attendees to vote for their favorite by placing a domino in the bowl beneath their choice. (The “voting booth” is pictured.) The choice was clear—the mosaic constructed with black dominos won in a landslide!
Putting the Pieces Together
With the mosaic design complete and the votes counted, the final step was to put theory into practice and build the mosaic. Pennock built a frame on which to assemble the mosaic and then gathered DIMACS faculty, postdocs, and staff for a brown-bag-lunch-and-mosaic-construction activity. The team set to work sorting and placing dominos, and in a few hours Domino Fred was complete. At right is the final mosaic constructed from real dominos. The portrait is about 4 feet tall and 3.3 feet wide.
About the construction process, Pennock commented, “It was harder than I thought it would be.” Any plans for constructing the high-quality 207-set mosaic, which would stand twelve feet tall, are on indefinite hold.
You can watch our one-and-a-half minute time-lapse video to see Domino Fred take shape.
Printable version of this story: [PDF]