 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
Issue Contents :: Around Tappan Square:: Page [ 1 2 3 4 5 6 ]
One
Continuous
Line
86,469 cities equals Nancy Dye
 |
Professor of Mathematics Robert Bosch and student Adrianne Herman '04 / photo by Sanielle Indovino '06 |
Many of us have attempted the challenge of creating a continuous line drawing without picking up our pencil or retracing a line. Scores of amoeba-like shapes can result from these exercises, followed by thoughts of "This can't be done!" Professor of Mathematics Robert Bosch and student Adrianne Herman '04 would beg to differ, however, and they've produced an impressive image of Mona Lisa to prove it.
In a paper to be published in Operations Research Letter in July, Bosch and Herman explain that most continuous line drawing exercises can be thought of mathematically. They point to the famous "traveling salesman problem" (TSP), in which the objective is to find the shortest route between multiple points, or "cities." As Bosch and Herman discovered, the method can also be used to create art. The pair developed a computer program that places points on a canvas so that when a line is drawn connecting them, the resulting image resembles a portrait. Finding the shortest line through all the points produces a likeness of the original image.
Bosch's hobby relates to his course offerings in the math department, particularly Optimization, also defined as the mathema- tical procedure(s) used to make a system or design most effective. The theory of mathematical programming–and the analysis of optimization algorithms–are applied to problems in the fields of medicine, finance, transportation, and telecommunications.
Bosch's interests, however, involve the nontraditional applications of optimization. Early last year, he wrote a computer program based on integer programming, in which black and white images are converted into thousands of tiny squares–like dominoes. The squares are labeled with numbers that represent black, white, and shades of grey. The computer then searches for an arrangement of dominoes that matches up with the numbers that describe the image. Using this program, Bosch has constructed dozens of portraits, including those of Martin Luther King, Jr. and Albert Einstein.
"I've always been interested in applying optimization to art problems and trying to create artwork," says Bosch. "For decades, integer programming has been used by operations research professionals to construct schedules, devise routes, and solve other large-scale planning problems. Over the years, it has saved corporations millions of dollars. And now it is being used to make artwork."
According to Georgia Tech researchers, challenges related to TSP have long in-trigued mathematicians. They were studied in the 1800s by Sir William Rowan Hamilton and Thomas Penyngton Kirkman, resulting in a mathematical puzzle called the Icosian Game. Players, using a wooden board with 20 holes and pegs, complete tours, or routes, using specified connections.
More than a century later, researchers introduced a breakthrough in solution methods for TSP that allowed them to find the shortest route through 49 "cities." Nearly 50 years later, another team of researchers solved a much larger tour– 15,112 German cities. Last year, Bosch and Herman solved, to near optimality, a TSP instance with 117,907 cities, which, when viewed from a distance, forms a portrait of Princess Maxima of the Netherlands.
"We began working on this project last June as part of an Award for the Integra-tion of Research and Education grant," says Herman, a performance and mathematics major.
"At the time we used our own algorithm for solving the TSP, but in the fall we began using a new method that produced much better portraits and allowed us to spend more time refining the process we used to place the "cities" on the canvas, which great- ly improved our resulting images. It was fun."
According to Bosch, portraits are the ideal form of TSP Art because they allow for areas of varying shades of grey. Landscapes and very dark pictures require more cities, which makes the problem harder to solve.
In addition to the portrait of Nancy Dye, other successfully reproduced images include DaVinci's Mona Lisa (consisting of 143,824 cities), Marilyn Monroe (117,907 cities), Howard Dean (29,725 cities), and several Oberlin mathematics professors.
Next Page >>