Forum
Dominizing Venus
By Robert A. Bosch
If you ask the proverbial man on the street to tell you what's happening in the month of April, there's a good chance you'll get one of the following answers: spring, showers, taxes, the start of baseball season. But if you ask a mathematics professor, you could get a very different answer.
April is Mathematics Awareness Month, a time when mathematics professors get especially pumped up about their subject matter. Some even wear "Math is Beautiful!" buttons, and they are absolutely right to do so.
Especially this year. You see, every Mathematics Awareness Month (MAM) has a theme, and the theme of MAM 2003 is "Mathematics and Art." In announcing this theme, the Joint Policy Board for Mathematics wrote:
"The connection between mathematics and art goes back thousands of years. The ancient Greeks and Romans used mathematics in sculptures and to aesthetically design buildings. In the 15th century, Leonardo da Vinci wrote, 'Let no one read me who is not a mathematician.' In the 16th century, Durer employed mathematics to introduce perspective in drawings. In the 18th and 19th centuries, mathematics was extensively used in the design of Gothic cathedrals, Rose windows, mosaics and tilings. In the 20th century, geometric forms were fundamental to the cubists and many abstract expressionists. In recent decades several award-winning sculptors have used topology as the basis for their pieces" [1].But what about the mathematics used and created by OR/MS professionals; did the Joint Policy Board miss anything? Is there a connection between OR/MS and art? Can any of our tools be used to create art? The answer to these questions is a resounding "yes."
Domino Artwork
The artist Ken Knowlton specializes in computer-assisted mosiacs [2]. Perhaps his best known work is a portrait of Scientific American's "Mathematical Games" columnist Martin Gardner that he made out of six complete sets of double nine dominoes. Knowlton presented the portrait to Gardner at G4G1, the first "Gathering for Gardner" conference, and a picture of it was used to decorate the back cover of the proceedings [3].
In January 2002, I devised a new, integer-programming-based method for constructing domino artwork, and in November 2002, I launched the company DominoArtwork.com [4]. In the past year I have constructed hundreds of pieces of domino artwork, from the small (9 sets) to the very large (100 sets). (To my knowledge, Knowlton's largest is a 24-set piece.)
In January 2003, I designed a 12-set portrait of Martin Luther King Jr. and supervised its construction by a crack team of 36 first- and second-graders, the students in Sharon Blecher and Gail Burton's "Open Room" at Eastwood Elementary School in Oberlin, Ohio. In August 2003, I will be building a 48-set portrait for ISMP 2003 in Copenhagen.
Figure 1 depicts a close-up of Botticelli's Venus that I constructed out of 100 complete sets of (virtual) double nine dominoes. Here's how it was done:
Figure 1: 5,500 dominoes = one Venus.
Step 1: I converted a 220 X 200 digital photo of Venus' head into PGM (portable graymap) format. In PGM format, each pixel of the photo has a grayscale value between 0 (completely black) and 255 (completely white).
Step 2: I converted the PGM file into a 110 X 100 table of numbers between 0 and 9. To do this, I partitioned the pixels into 2 X 2 squares, computed the mean grayscale value for each square, and then converted the means to integers between 0 and 9. (Why 110 X 100? There are 55 dominoes in a complete set of double-nine dominoes, and each is comprised of two squares. So 100 complete sets of double-nine dominoes can be used to tile a 110-row, 100-column board. Why integers between 0 and 9? Each square on a double-nine domino has between 0 and 9 dots on it.)
Step 3: I formulated an integer program that, when solved, finds the arrangement of dominoes that is closest to the table of numbers. Figure 2 illustrates this process. The top part is Venus' right eye in grayscale. The middle part is the corresponding table of numbers. And the bottom portion — a close-up of a small section of Figure 1 — is Venus' right eye, done in dominoes.
Figure 2: Eyeing the arrangement of dominoes.
The IP: Decision Variables
Each domino can be referred to by an ordered pair (m,n) where m≤n; m and n specify the number of dots on the domino's squares. In a complete set there are 10 doubles and (10 2 ) = 45 non-doubles. Each double has two orientations: v (vertical) and h (horizontal). Each non-double has four orientations: v1 (vertical with the lower-numbered square on top), v2 (vertical with the lower-numbered square on the bottom), h1 (horizontal with the lower-numbered square on the left), and h2 (horizontal with the lower-numbered square on the right).
The decision variables are as follows: Xm,n,o,i,j equals 1 if domino (m,n) is placed in orientation o with its top left square in the row-i-column-j square of the board and 0 if not. It is easy to show that if the board has 110 rows and 100 columns, then there are 2,179,000 decision variables!
[For detailed information on the objective function and the constraints, contact the author. The goal of the IP is to minimize the total penalty given the cost of placing domino (m,n) in orientation o with its top-left square in the row-i-column-j square of the board. One way to measure costs is to use a squared 2-norm. There are two types of constraints. The "type-one" constraint states that domino (m,n) must be used 100 times. (Recall that we are using 100 sets of dominoes.) There are 55 type-one constraints — one for each distinguishable domino. The "type-two" constraint states that the row-i-column-j square of the board must be covered by exactly one domino. There are 11,000 type-two constraints — one for each square of the board. (The type-two constraints for corner squares and edge squares have fewer terms than the type-two interior constraints.)]
The IP: Results
The Venus IP took about 10 hours to solve using CPLEX 6.6 on an 800 Mz Pentium III computer with 384 MB of physical memory. This is typical. Although the integer programs are quite large, they are usually very easy to solve. In most cases, the optimal solution to the LP relaxation is integer-valued.
Usually, the solution is of high quality. For Venus, the average error over all 11,000 squares was only 1.18. For her right eye, the average error was 1.22. To see more domino pictures, go to www.dominoartwork.com.
References
- Math Forum, Mathematics Awareness Month, 2003, Announcement-January 2003, www.mathforum.org/mam/03/announce.html.
- K. Knowlton, Knowlton, 2003, www.artists-nh.com/knowlton.htm.
- E. Berlekamp and T. Rodgers, 1999, "The Mathemagician and Pied Puzzler: A Collection in Tribute to Martin Gardner," AK Peters.
- R. Bosch, 2003, "Domino Artwork," www.dominoartwork.com.
Robert A. Bosch (bobb@cs.oberlin.edu) is a professor in the department of mathematics at Oberlin College in Oberlin, Ohio.
OR/MS Today copyright © 2003 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Rd., Suite 220, Marietta, GA 30060 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com
Web Site © Copyright 2003 by Lionheart Publishing, Inc. All rights reserved.