Skip to main content

When the Mona Lisa Is NP-Hard

Bob Bosch and Tom Wexler have developed a new way to make your favorite masterpieces into connect-the-dots puzzles. All you need is a little bit of quantification and a lot of computing time.

The Mona Lisa as a solution to the figurative tour problem (left) and figurative braid problem (right).

Credit:

Robert Bosch and Tom Wexler

This article was published in Scientific American’s former blog network and reflects the views of the author, not necessarily those of Scientific American


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. Dominoportraits 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.


On supporting science journalism

If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.


The Mona Lisa as a piece of TSP art

Left: the cluster of dots for a Mona Lisa TSP. Right: the optimal tour. Credit: Robert Bosch and Tom Wexler

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.

Left: a grid of 1395 points. Right: a figurative tour that resembles the Mona Lisa. Credit: Robert Bosch and Tom Wexler

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.

Botticelli's Venus as a figurative tour. Credit: Robert Bosch and Tom Wexler

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.

Marilyn Monroe as a figurative braid problem

Marilyn Monroe as the solution to the figurative braid problem with three different sets of constraints on the shapes of the braids. Credit: Robert Bosch and Tom Wexler

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.

For more about opt-art, Bob Bosch and Craig Kaplan can help you fall down that rabbit hole.