I’ve always thought the Mona Lisa would be better as a connect-the-dots puzzle, haven’t you? Luckily for us, mathematician Robert (Bob) Bosch and computer scientist Tom Wexler of Oberlin College are pioneering a technique to turn your favorite masterpiece into a tangle of dots and crossing lines. They call it the figurative tour problem (FTP). Their preliminary paper on the method will appear in the proceedings of the 2015 Bridges math-art conference and is currently available online at Bosch’s website.
The new technique is an expansion of the existing genre of optimization, or opt, art. Opt art uses computational constraints to generate interesting images. Domino portraits and mosaics are one form, but the closest opt-art analogue of the FTP is traveling salesman problem (TSP) art. The goal of the traveling salesman problem is to find the shortest trip that goes through an arbitrary set of points, like the path a traveling salesperson might have taken in the dark days before they could just set up an Etsy shop.
To create TSP art, you turn a desired picture into a patch of clustered points and then let a computer find a TSP-optimal path between them, as in the picture below.
As Bosch and Wexler write, “Even though this tour is the best one possible and does indeed resemble the target image, it doesn’t achieve as good a likeness as the points do alone.” It seems like kind of a waste to solve the traveling salesman problem just to make the picture worse, so they decided to change the rules of the game.
Instead of clustering the points in their image, they start with a regular grid of points. The object of the game is then to connect them not with a path that solves the traveling salesman problem but with one that visually resembles the target image. The path should still hit each point exactly once, but now the winning trip will probably be longer than the TSP-optimal path.
To quantify the problem, Bosch and Wexler convert the target image into grayscale and assign every point of the grid a number between 0 and 1 that represents how dark or light the picture is in the corresponding region. After some experimentation, they decided to restrict edges to King’s or Knight’s moves, and some further experimentation helped them determine how to assign a weight to each section of the grid corresponding to how much the edges darken it. The researchers use the Gurobi Optimizer to find paths that minimize the total difference in brightness between the grayscale target image and the FTP image.
As you might imagine, the figurative tour problem is computationally expensive. In fact, with the size of the grids they were using, Gurobi just couldn’t get good results. ("I'm not blaming Gurobi for this," Bosch wrote in an email. It's a hard problem!) Instead of trying to optimize the path over the entire grid, Bosch and Wexler decided to look at smaller chunks separately and then carefully stitch together the paths they got for each piece to find a good solution for the whole grid. The process still takes a long time, but at least it happens. “With the sliding window method, I can get a decent figurative solution in a day or two,” Bosch wrote.
Bosch and Wexler’s paper also describes a similar new opt-art method called the figurative braid problem: instead of connecting all the points in a grid with one path, they start a path at each point in the top row and eventually connect each top point to a point on the bottom, hitting exactly one point from each row on the way down. The strands are separate from each other so, so like the strands of a braid, they intertwine as they run from top to bottom. To my eye, the images don’t look quite as much like the target pictures as the FTP solutions do, but the curved lines are distinctive and visually pleasing. They'd be perfectly at home on a dorm room wall.
For the theoretical computer science geeks: Bosch hasn’t studied the computational complexity of the FTP, but his guess is that it’s NP-hard. That’s my guess too; it seems like it’s not so different from the TSP—there’s a slightly different function to optimize, but the crux of the problem is similar. It’s just a guess, but I like the idea that drawing the Mona Lisa is NP-hard.