Lawn Theory 101

Four years in this house and I have yet to find a Hamiltonian circuit of the lawn. Curse you NP-completeness!

Explanation: In graph theory, a Hamiltonian circuit is a path that starts at a point in a graph, travels through all other points in the graph exactly once, and returns to the starting point. Determining whether such a path exists in a graph is an example of what's called an NP-complete problem, which means (among other things) that there is no known algorithm of polynomial time complexity for solving it. In other words, it's really hard.

Consider my lawn to be a collection of points, with each point connected to the points closest to it by an edge. Now it's no longer a lawn, it's a planar graph! Thus, we can apply graph theory, and the most efficient way to mow my lawn is the Hamiltonian circuit that starts (and ends) closest to my garage.

You know, for $30 a mow, you can just pay the local lawn guy to do it while you play computer games.

I really should be thinking of it as a Travelling Salesman Problem instead. In that case, I attach a weight to each of the edges in the graph (the length of the edge) and then solve for the shortest tour of the vertices. It's still an NP-complete problem, but now I not only mow each part of the lawn only once, I also travel a minimal distance in doing so. I can't solve it, but if I could it would give me a better answer.

You think about this stuff while vacuuming, too, don't you?

Yes. And mopping the floor. Mopping the floor is easier to visualize because the floor is neatly broken down in to tiles. It's more difficult, however, because you have to take into consideration that you can never stand in a place where you've already mopped.

This is why mathematicians never work as landscapers or housecleaners.

Interestingly, those jobs are often taken by immigrants who speak little or no English, and therefore have better communication skills than most math majors.

It kind of sucks the fun out of things when you make fun of yourself.

It sure does!

Can we talk about toasters now?

No.