Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

The Mathematics of Lawn Mowing

timothy posted more than 2 years ago | from the go-fast-turn-left dept.

Math 514

Hugh Pickens writes "I enjoy mowing my six-acre lawn with my John Deere 757 zero-turn every week, and over the course of the last five years of mowing I have come up with my own most efficient method of getting the job done which takes me about three hours. While completing my task this morning, I decided after I finished to research the subject to discover if there is a method for determining the most efficient path for mowing, and found that Australians Bunkard Polster and Marty Ross wrote last summer about an elegant mathematical presentation of the problem of mowing an irregularly shaped area as efficiently as possible. First we simplify our golf course mowing problem by covering the course with an array of circles with each circle radius equal to the width of the mower disc. Connecting the centers of the circles produces an equilateral triangular grid, with vertices at the circle centers. Following a path consisting of grid edges, there will necessarily be a fair amount of overlap so the statement of the problem is to minimize the overlap by minimizing the number of vertices that are visited more than once which Polster and Ross say is easily achieved by well-known computer search algorithms. Any other tips from Slashdot readers?"

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered


Here's a tip... (5, Funny)

nbetcher (973062) | more than 2 years ago | (#37006238)

... hire someone to mow it for you. :)

Re:Here's a tip... (-1)

Anonymous Coward | more than 2 years ago | (#37006262)

But I thought all the Mexicans were going home!

Re:Here's a tip... (1, Insightful)

M. Baranczak (726671) | more than 2 years ago | (#37006276)

Here's another tip. More of a rhetorical question, actually: what the hell does anybody need a six-acre lawn for? Can you honestly say that it provides you with more enjoyment than, say, a half-acre lawn?

Re:Here's a tip... (3, Insightful)

Aladrin (926209) | more than 2 years ago | (#37006350)

Absolutely. A half-acre is barely enough to do any sports-like activities. There's a very good chance that the ball/disc/boomerang/whatever will end up in the neighbor's yard.

At best, it's a pain to go around and get it, and everyone waits while one person has a good run, unbalancing everything.

At worst, you have a cranky neighbor or break something in your neighbor's yard.

So yeah, having a big yard can make a difference.

If all you do is barbecue, then a 1/2 acre yard is more than enough, though.

If only Americans had heard of parks. (-1, Troll)

Anonymous Coward | more than 2 years ago | (#37006714)

This is a fantastic example of how Americans take a simple problem and absolutely fuck up the solution.

So these Americans want to partake in some outdoor activity that requires a bit of open grass. Their solution? Buy a 6 acre lawn, pay property taxes on this land, buy a lawnmower, buy fuel for the lawnmower, buy fertilizer for the lawn, and waste hours each week mowing the lawn. Even if they pay somebody to maintain it for them, it's still a huge waste of money, time, and effort.

What do people in sensible countries do? They build parks, and everybody in the vicinity contributes a small amount of money towards its upkeep, without the burden falling directly on their shoulders. They can go use it whenever they want, and such parks are large enough that thousands of people can partake in all sorts of sports or other activities at the same time, from barbecuing, to playing catch, to even playing golf, without interfering with one another.

Oh, wait. Parks are probably too "socialist" at best, or "communist" at worst, for most Americans.

Re:If only Americans had heard of parks. (1)

m.ducharme (1082683) | more than 2 years ago | (#37006748)

Yeah, but then if Americans built parks, they'd have to get to know their neighbours.

Re:If only Americans had heard of parks. (1)

GospelHead821 (466923) | more than 2 years ago | (#37006798)

I agree that public parks are a much better solution than large yards. Part of the problem, however, is that when you're choosing a new home, access to public recreation can be just one of many factors to choose from. It might be more important to me to be close to public transportation, the grocery store, my children's school, my job, etc. Since Americans have previously NOT chosen to build spacious parks everywhere, that might leave me without adequate access. I might, however, be able to find a larger lot of land meeting my other criteria. It's not an ideal solution but the alternative is choosing a smaller lot and then immediately start rallying for land to be purchased or rededicated for a park. Even if that works, though, I wouldn't be able to enjoy a large, open space for a few years.

Re:Here's a tip... (1)

level_headed_midwest (888889) | more than 2 years ago | (#37006454)

Absolutely. The biggest advantage to a larger lawn is that you are guaranteed to have more space between your house and your neighbor's houses. The second advantage that going and playing outside is much easier in a larger lawn. (I know, go outside and play, who does THAT any more?) A half-acre lawn generally means you have at best 20 yards or so between houses, since most half-acre lawns are in town. That's really not a lot of room and the houses are fairly densely packed together in that area. Try to go outside and play pitch and catch in such a lawn. If you slip up at all, you broke the window in the Jones' house or put a dent in Mr. Smith's Buick. Not fun. A six-acre lawn guarantees that you are more like a hundred yards between houses. Also, if you value privacy and quiet, there's a lot more of that when you have a large lawn and thus a larger distance between neighboring houses. You could have a half-acre lawn in a 100-acre chunk of woods and have the privacy, peace, and quiet, but in practice, most people have a few acres of lawn around their house in such a setup just because it's nice to have a lawn to play around with the kids. Chasing the baseball into the woods isn't generally too much fun either.

Re:Here's a tip... (1)

houghi (78078) | more than 2 years ago | (#37006524)

Absolutely. The biggest advantage to a larger lawn is that you are guaranteed to have more space between your house and your neighbor's houses.

Not if the lawn is just as wide as your house. So it is not a guarantee.

Re:Here's a tip... (1)

level_headed_midwest (888889) | more than 2 years ago | (#37006562)

Unless you're buying a road or power line easement, not very many six-acre tracts are 2/3 mile long and 75 feet wide.

Re:Here's a tip... (1)

Anonymous Coward | more than 2 years ago | (#37006592)


Re:Here's a tip... (0)

Anonymous Coward | more than 2 years ago | (#37006630)

Pretty awesome story. Thanks for the link.

Re:Here's a tip... (1)

Stickybombs (1805046) | more than 2 years ago | (#37006674)

Sure there are exceptions, but many townships (at least the midwest US) have ordinances that limit property splits to a 4:1 depth to width ratio. So the worst your six acre lot could be in that case is 256 feet wide.

Re:Here's a tip... (0)

Anonymous Coward | more than 2 years ago | (#37006618)

I have 12 acres of trees and about an acre of 'lawn', mostly around the house and shop... The belt around the home is as a sort of crude fire-break and then there's a sizable strip down the hill so as to open up the view to the mountains... So my lawn mowing takes about 45 minutes including a couple of trips to the compost pile to empty bags... I can say that it's nice to have a forest, to isolate us from the neighbors, provide privacy, shelter from the wind, etc... Unfortunately, the forest brings with it other issues... Most significantly, wildlife... Some good, some not so good... For example, we regularly find cougar scat in the woods, and paw prints in the garden... A grizzly bear has been seen wandering through the various yards.. This has ramifications on my son's ability to go off and explore, like a boy should... Our forest is fairly natural, and left to its own devices. Unfortunately, that means a fair amount of downed trees providing ladder fuel for a ground fire.. It means I need to engage in certain forest management activities within a certain radius of the home...

It also means, and more to the point, that my lawn is a fairly irregular shape and my mower is not a zero-radius turn mower, so I have a turn radius greater than the width of the mowing deck (52" deck). It means I end up making a lot of long turns (if I want to make a 90 degree left turn, I go beyond where I want to turn, then do a tight right turn, and end up going straight perpendicular to where I started)... That consumes more time and fuel... Though not enough to make it worth my while to invest in a zero radius turn mower..

My lawn is not a beautiful masterpiece. It is a flat piece of ground intended to keep the forest at bay. Ultimately, I don't really care what my lawn looks like. It's on a slope so I can't really recreate on it.

Re:Here's a tip... (0)

Anonymous Coward | more than 2 years ago | (#37006858)

This cuts to the core of the issue.

1. If this is an unpleasant chore, sell the fancy tractor and hire out the job to some folks who need the money.

2. If this is a pleasant chore, there is no need to minimize the time, just enjoy your life style

3. If this is just some land you have and don't know what to do with it, lease it to someone who has horses, cows, sheep, or goats. They can turn it into a hay field, and maybe at the end of the year you get some nice, organic meat.

Neat first steps... (1)

BlackTriangle (581416) | more than 2 years ago | (#37006246)

But it's such a tease... what computer algorithms are referred to near the end of the article? I can't remember my intro algo's class :(

Re:Neat first steps... (1)

TapeCutter (624760) | more than 2 years ago | (#37006776)

DRTFA but assuming the circles are laid out to cover the entire lawn then it's an unconstrained 'Travelling salesman' problem, if not then it's constrained TS problem.

Give it a few tries and go with what's fastest (2)

Shadow of Eternity (795165) | more than 2 years ago | (#37006252)

Believe it or not sometimes people are better at solving certain problems than computers. This is one of those fuzzy problems with lots of irregularities that a human is excellent at working out with just a little help from a stopwatch.

Re:Give it a few tries and go with what's fastest (1)

couchslug (175151) | more than 2 years ago | (#37006456)

"Believe it or not sometimes people are better at solving certain problems than computers. "

"Kill the heretic! Kill him! Persecute! Kill!"

Re:Give it a few tries and go with what's fastest (1)

Oswald (235719) | more than 2 years ago | (#37006910)

I second this post. There are too many options/variables when you mow a large irregular space and too many possibilities that won't be considered by one-algorithm-fits-all solutions. How much is your mower's maneuverability degraded as speed goes up--would you be better off with a solution that had more straight lines but let you go faster? How about that little patch that sticks off the northwest corner--are you better off fitting it into the big pattern, or do you leave it until last, then deadhead over to get it separately? What is your system for trimming up the portions your big mower can't get to (or are there any of those?)--is it better to get every last bit you can with the zero-turn, or since you have to get the walk-behind out anyway, are you just wasting time getting every last blade you can with the big mower?

I think trying to solve this with a computer is like writing a program to compose an email to your mother. You probably get better results faster if you just do it yourself.

Simplest solution (0)

Anonymous Coward | more than 2 years ago | (#37006284)

Own less lawn.

Interesting Story! (3, Insightful)

MyLongNickName (822545) | more than 2 years ago | (#37006298)

First, let me say that I do like this type of story. Interesting, thought provoking, nerdy and mathematical in nature.

I will also preface what I am about to say by noting that people are free to make whatever life tradeoffs they want.

At the same time, I really wonder why anyone would want a property that takes three hours just to cut the grass. Life is short, why spend it maintaining a large property. I make low six figures now and could afford a lot more of a house than I have, and even when I upgrade to a nicer neighborhood next year will still way underbuy what the bank wants me to borrow.

If you are stinking rich and want the large property, go ahead... but hire someone to do it for you. Your time is more valuable than the cost of having someone cut your grass. Give some teenager or out of work adult the opportunity to earn some money. That is the real win-win of capitalism.

Finally, the article linked to seems light on the math itself, but seems very descriptive. I don't know that there is a purely mathematical solution to the problem but wonder if genetic algorithms would get you to where you want to be. I also wonder if you have a yard like mine with tree roots all over the place would change the outcome :)

Re:Interesting Story! (2)

brunes69 (86786) | more than 2 years ago | (#37006352)

For many people (especially with a ride on), mowing the lawn is not so much of a chore but an escape, a way to be out away from work, the wife, kids, noise... to have a couple of beers, listing to some tunes, basking in the sun - just in general relax for a few hours. It's stress relief. And the type of people with 6 figure incomes usually need it the most.

Now, i am not one of those people.. I get my stress relief playing some 360. But everyone has to have their own outlet, and I know lots of guys who say it is the weekly lawn mow.

Re:Interesting Story! (2, Insightful)

Anonymous Coward | more than 2 years ago | (#37006682)

Lawn mowing is a job that you can complete on your own that requires no meetings, team discussions or 300 e-mails before the project can even start. thenyou can step back and admire your work, knowing 37 other people will not take credit for it. ;o)

Re:Interesting Story! (1)

G-News.ch (793321) | more than 2 years ago | (#37006396)

the answer is right there in the OP: "I enjoy mowing..." Why do people eat too much and become fat? They enjoy it. Why do people drink to much an become drunk? They enjoy it. Why do people spend too much? They enjoy it. Mankind is not rational and there is no need to be. If the guy enjoys mowing his huge lawn, let him do it.

Re:Interesting Story! (1)

mattgoldey (753976) | more than 2 years ago | (#37006398)

Apparently you failed to even read the first three words of the summary... "I enjoy mowing"

Re:Interesting Story! (3, Funny)

mabhatter654 (561290) | more than 2 years ago | (#37006810)

If he enjoys mowing then there is no optimum solution. The BEST solution is one that shows the NEIGHBORHOOD you are better than them.

Go for the cross-cross checkerboard pattern... REAL LAWN FANS don't use circles! The problem is not efficiency, but how to mow the lawn and the trim around obstacles without leaving "tracks" or "foot prints" and without those tack circles around everything...

The correct answer may mean moving trees, etc...

Re:Interesting Story! (1)

Shimbo (100005) | more than 2 years ago | (#37006406)

Your time is more valuable than the cost of having someone cut your grass. Give some teenager or out of work adult the opportunity to earn some money. That is the real win-win of capitalism.

You missed the part where he said he enjoyed doing it. Not doing what the hell you like because your time is too valuable would be my idea of hell.

Re:Interesting Story! (2)

Arlet (29997) | more than 2 years ago | (#37006458)

If he enjoyed doing it, why is he looking for the most efficient method possible ?

Re:Interesting Story! (1)

Jah-Wren Ryel (80510) | more than 2 years ago | (#37006488)

If he enjoyed doing it, why is he looking for the most efficient method possible ?

So he can do his neighbour's too.

Re:Interesting Story! (0)

Anonymous Coward | more than 2 years ago | (#37006680)

That may be what he enjoys. The complex problem of finding out how to do it most efficiently.

Enjoyment for some people comes from working out solutions to interesting/real-life problems.

split zoning (1)

alphatel (1450715) | more than 2 years ago | (#37006302)

I can't speak to mathematical models of efficiency but I can tell you about landscapers models of gas and employee efficiency.
Use trimmers and small mowers to shape up the irregular areas until they reach a common area or edge.
Allow the riding mowers to tackle the larger squared zones
Of course none of this accounts for the grass, which must be hauled with an attached trailer on the riding mowers and regularly emptied regardless of the efficiency pattern.

Re:split zoning (1)

thermopile (571680) | more than 2 years ago | (#37006408)

Agreed. Even at home, my mantra is, "Minimize turns."

Do 1 or 2 laps around the outer edge to give you a buffer so you don't spray grass all over the sidewalks, etc., and then choose the longest dimension of the ~rectangular shape you have left. Make long passes back and forth along this edge, alternating left, right, left, right. (If you're not bagging, this means you will run over some of your discharge sometimes, but that's OK as long as the grass isn't too tall.)

Using this method reduced the time necessary to mow my 1/3 acre by about 10%. Fairly handy.

Re:split zoning (1)

MagicM (85041) | more than 2 years ago | (#37006540)

This is my method as well, for the same reasons.

However I do feel like taking "minimize turns" to the extreme would be even more efficient. Starting at the outer edge and going inward in more or less a spiral should eliminate turns completely. You just end up with an odd pattern for your neighbors to talk about.

Re:split zoning (1)

statichead (66370) | more than 2 years ago | (#37006698)

Looks great on paper but the real world chooses differently, look at some farm crops, long straight swaths, easy to manage.

A human would spend so much time trying to re evaluate the lawn as he goes it would lead to wasted time and inefficiency. Also machines may not be able to physically follow the "ideal" line.

All that turning would:
slow down the machine
introduce a lot of overcut of areas that have already been mowed. ( not to mention that a machine may not be able to make the turns required to be 100%

Straight lines maximize the amount of grass cut over time and reduces complexity so the operator can drink beer.

But is it a GERMAN study? (0)

Anonymous Coward | more than 2 years ago | (#37006324)

TITS That ist what ist required for this to have any shot at validity. I mean, it ist true that stinkin' armpits should not be allowed on a plane, but it shouldn't for a wholly different reason. Same for the mathematics of lawn mowing. TITS

My lawn mowing is further complicated... (1)

SwedishChef (69313) | more than 2 years ago | (#37006334)

Because I live in a US county that publicly owns two hydro-electric dams our electric power rates are low enough to make it much more economical to use an electric-powered lawn mower instead of a gasoline-powered lawn mower. The safest method of mowing the grass would be to ensure that the power cord always stays out of the way of the grass-cutting head of the mower. This complicates the efficient mowing technique because, in general, it's better to simply mow so that the power cord is always on the freshly mowed grass and never on the soon-to-be-mowed grass.

I wonder what effect this would have on the system.

Simplification probably invalidates the math (1)

bbartlog (1853116) | more than 2 years ago | (#37006344)

By treating the lawn as a set of circular areas of radius equal to the mower disc, they eliminate all possible routes that would involve driving the mower on some path other than vertex to vertex. And I expect it would not be hard to construct a lawn where the best path involved just such a route. As constructed I think the problem is actually kind of boring (which is not to say I can solve it!); it would be more interesting if they had come up with some way to attack the optimization problem without turning it into something out of graph theory.

Doesn't look good (5, Funny)

Arlet (29997) | more than 2 years ago | (#37006368)

The 'optimal' solution has the mower finishing in the middle of the lawn, which is usually not where you want to leave it parked.

Re:Doesn't look good (2)

bgarcia (33222) | more than 2 years ago | (#37006602)

Unlike the "painting the floor" task, it's not that much of an issue here.

Re:Doesn't look good (1)

Arlet (29997) | more than 2 years ago | (#37006700)

Not much, but assuming you want to move the mower back, the proposed solution isn't optimal because your traveling twice over the same strip of grass.

Re:Doesn't look good (0)

Anonymous Coward | more than 2 years ago | (#37006994)

I used to mow the neighborhood lawns when I was in high school. I would optimize the each yard based on a variety of factors. Since I used a bagging mower, I wanted to be able to drag the bags back to the front of the house. The best bet was to start in the back of the house, do the furthest rows, bag the grass, and throw the bag towards the house the approximate distance to where I would need to change the next bag. This way, I had to go to the front of the house to dump the bags half the number of times. I think I probably saved 3 minutes per lawn doing it this way!

Fenway (0)

Anonymous Coward | more than 2 years ago | (#37006372)

Although Dykstra's algorithm is great for the most efficient airline flights between airports..I like the symmetry patterns of Fenway Park..although I only have to cut 1/2 acre.

buy 3 goats (0)

Anonymous Coward | more than 2 years ago | (#37006378)

They don't use gas or waste your time.

Little issue... (1)

LordNacho (1909280) | more than 2 years ago | (#37006390)

How does the circular mower cut corners? Don't most people have a corner of smaller radius that their imaginary circular lawnmower?

Shouldn't the problem be how to sweep a straight line of some given width to cover an area? I'm guessing the circular mower is some sort of simplifying assumption. Never had a lawn before, so no idea.

Re:Little issue... (1)

Arlet (29997) | more than 2 years ago | (#37006418)

TFA has a picture of the lawnmower. It is circular, and not at all imaginary.

reality (1)

queazocotal (915608) | more than 2 years ago | (#37006394)

This neglects the reality that even with zero turn mowers, there is some cost to turning.
You can't make a right angle turn at full speed.
There isn't a mathematically correct solution unless you correctly model the costs of turning.
If you're doing it 'by hand' - then you also need to model the cost of screwing up.
It may be that comparatively simple schemes - such as an interleaved raster scan may be
in practice optimal for a human to mow it.

IME (1)

Aladrin (926209) | more than 2 years ago | (#37006402)

In my experience (with 1-acre and 4-acre sections to mow) there is a little you can do to optimize the route, but in general, you want to end up with the clippings shooting toward the center of the lawn so it's easy to rake. (The bags on the mowers are a pain because you have to empty them so often.) So the perfect path in the article is marred by the fact that you then have to either re-mow some of it to shoot the clippings in the right direction, or get out a blower and spend just as much time doing that.

Re:IME (1)

chalker (718945) | more than 2 years ago | (#37006814)

Strange, nobody I know collects or picks up the clippings. That's what recycling mowers are for.. they chop them up fine enough that you can't even tell they are on the lawn. It lets the nutrients stay on the lawn, and you don't have to worry about what to do with the waste, so it's the best 'environmentally' friendly solution.

Re:IME (1)

foniksonik (573572) | more than 2 years ago | (#37006842)

If he mows every week he could be mulching and leaving the clippings. One week grass growth us pretty minimal no matter where you live - maybe an inch or two.

Re:IME (1)

zippthorne (748122) | more than 2 years ago | (#37006958)

if you hate bags, maybe you should try getting mowers with a "mulching" setting. No point in throwing away all that free fertilizer.

There's really no point in bagging unless you're trying to gather up vegetative waste for a purpose, like perhaps a compost pile or something. "Filling up the county dump with yard waste" is not a worthwhile purpose.

3 hours of mowing? Enjoy? (0)

Anonymous Coward | more than 2 years ago | (#37006432)

"I enjoy mowing my six-acre lawn with my John Deere 757"

Wait, he enjoys that?

My goal with my lawn, year by year, is to slowly but surely destroy it. I rip it up and replace it with gardens, trees, or crushed stone with ornamental larger rocks, sometimes with ferns and moss around the edges. The remaining grass is entirely naturally selected -- that is, if it survives without additional water, fertilizer, aeration or other manual interference other than the occasional mow, it lives. If not, it can go ahead and die, to be replaced by the stuff that can survive. Since I bought this house I've decreased the total lawn area by about 25%, and my front lawn is down to about 40% of the original area (60% of it is replaced). What time I spend maintaining the non-lawn areas is expended yanking the occasional weed out of the garden, trimming bushes, or raking the gravel and arranging the ornamental boulders. It looks quite nice in the front. The back needs a lot more work (too much grass), but most people don't see it, so I can neglect the mowing a bit.

My optimal lawn mowing strategy is to mow less. Permanently.

Are you a salesman? (0)

Anonymous Coward | more than 2 years ago | (#37006434)

It sounds (after those particular assumptions) like you want to solve the Traveling Salesman Problem, in particular the special case with Euclidean 2d distances (more or less, depending on hills). "Computer search algorithms" is a little bit of a weasel word... I believe these are exactly solved in practice on moderate-size instances using integer linear programming (ILP) techniques, the work of Bill Cook and co-authors is likely useful. From a theoretical (but not so important) perspective: the problem is NP-complete but admits an "approximation scheme." See http://en.wikipedia.org/wiki/Travelling_salesman_problem

Re:Are you a salesman? (0)

Anonymous Coward | more than 2 years ago | (#37006678)

Thw Traveling Salesman approach is a least distance problem but unless you have particular via points, seems unrelated to the coverage problem.

Circles? (1)

Dunbal (464142) | more than 2 years ago | (#37006440)

What? Floodfill ftw.

Re:Circles? (1)

hellop2 (1271166) | more than 2 years ago | (#37006778)

FTA: "Puzzle to ponder: Suppose you have a lawn that is 200 square meters in area and your mower disc is 70 cm in diameter. Show that any mowing path for this lawn must be at least 280 metres in length."

Mower is .7m. Imagine the simplest lawn, one with no turns, the width of the mower. So x*.7m = 200m => x = 285m.

Who cares? (1)

Anonymous Coward | more than 2 years ago | (#37006464)

When America collapses, people with 6-acre lawns will soon find very persuasive arguments that they should be sharing their land with the less lucky.

Now solve the problem... (1)

John Hasler (414242) | more than 2 years ago | (#37006484)

...for a tractor-haybine combination with an 80" swath and a 20' turning radius.

Re:Now solve the problem... (0)

Anonymous Coward | more than 2 years ago | (#37006612)

Make that a general solution! My mowing deck is 60" and my 3 acres is littered with fixed and temporary objects. I utilize my estate with antenna experimentation. Most of the fruit from the trees I cultivate goes to both domestic and wild animals. I don't consider it a lawn, it is a meadow. The reasons for mowing are to keep the Tick population in check and minimize fire risks. -- W8CCW

Travel and sell much? (1)

daveagp (2431120) | more than 2 years ago | (#37006498)

It's a case of the Traveling Salesman Problem http://en.wikipedia.org/wiki/Travelling_salesman_problem [wikipedia.org] On the one hand it is the special case with Euclidean 2d distances (more or less, depending on hills). But also, it is the special case where all point-point distances are equal, depending on what exactly you meant by 'grid', which is called Graphical TSP. "Computer search algorithms" is a little bit of a weasel word... but as far as I know TSP instances are exactly solved in practice on moderate-size instances using integer linear programming (ILP) techniques, the work of Bill Cook and co-authors is likely useful. From a theoretical (but not so important) perspective: the 2d Euclidean problem is NP-complete but admits an "approximation scheme." I am not sure about the doubly special case you present, but my gut feeling would be it's also NP-complete.

And picking up golf balls (0)

Anonymous Coward | more than 2 years ago | (#37006560)

I've had a similar problem which I guess may be easier solved intuitively:

I'm at a golf course at the chipping green, and chip a bucket of balls onto the green. Now I wish to pick up those balls and put them back in the bucket. What is the most efficient path to take to pick up the balls (especially if I'm not a good chipper and some balls are spread out significantly).

If you are thinking about lawn care (1)

assertation (1255714) | more than 2 years ago | (#37006572)

If you are using your wet RAM thinking about about lawn care you can possibly take it as a sign that your youth and the more interesting times of your life are over.

The single quickest method for mowing (1)

Anonymous Coward | more than 2 years ago | (#37006574)

The quickest method I've found for mowing my lawn is to hire someone else. It literally takes me only 3 to 5 minutes to write the check, and there is no geometry involved.

act greeen. google does. (1, Offtopic)

Spovednik (1247806) | more than 2 years ago | (#37006608)

mowing 6 acres with a lawn mower? that should be a crime in its own. invest in 20-25 goats and a fence. not sheep. sheep are stupid and they smell. goats are smart. you'll find that looking at them is really relaxing. they'll also keep your lawn at golf-course grade length. price? sell your john deere and you should have enough to buy the lot.

Homer Simpson-- (-1)

Anonymous Coward | more than 2 years ago | (#37006644)


Traveling Mower (1)

jamescford (205756) | more than 2 years ago | (#37006654)

It could be described as a variant of the Traveling Salesman problem, where each node is a mower-sized swath of grass and your object is to visit very node, returning to the starting one...

Re:Traveling Mower (1)

karnal (22275) | more than 2 years ago | (#37006728)

There's actually no need to return to the starting one however, as it is already mowed. The goal would be to mow every node in the most efficient path possible. Start and end node could vary depending on speed of solution to problem.

Re:Traveling Mower (1)

zippthorne (748122) | more than 2 years ago | (#37006970)

You want the start and end node to be the same, so you can put the mower shed right next to it...

Re:Traveling Mower (1)

SlothDead (1251206) | more than 2 years ago | (#37007002)

No, since you want to park the mower in the same spot at the end.

(Unless you build two sheds in different locations to optimize your mowing path...)

Me too! (0)

Anonymous Coward | more than 2 years ago | (#37006706)

I enjoy eating gruel out of a plastic bowl placed on the tarp outside my tent every morning in the tent city where I live.

Cam software (0)

Anonymous Coward | more than 2 years ago | (#37006710)

The solution to this is very similar to what a cam package would produce.

Lawn? (4, Insightful)

Rising Ape (1620461) | more than 2 years ago | (#37006732)

Six acres isn't a lawn, it's a field... anyone else get the impression this guy just wanted a reason to say "I have a six acre lawn"?

Best solution (5, Insightful)

Charliemopps (1157495) | more than 2 years ago | (#37006752)

The best solution: don't mow it.
Why the hell do you have 6 acres of grass? Plant some trees for christs sake.

Turning losses (1)

findoutmoretoday (1475299) | more than 2 years ago | (#37006802)

Even if the zero-turn is very impressive it is not the mathematical model.  When turning the width of the combined blades and the average speed will be reduced, making each turn sub optimal.  As a boy I used a(n unsafe,  think of the children) mower on a rope turning perfect spirals with a distant supervisor and finished off the in betweens in direct supervision mode.

livestock (0)

Anonymous Coward | more than 2 years ago | (#37006804)

I found cows, goats and fowl to do a good job and save me lots of time.

You have an answer (1)

nedlohs (1335013) | more than 2 years ago | (#37006820)

from a mathematician with a few dozen published papers and half a dozen published books on mathematics.

So now you ask slashdot just to make sure???

there ya go (0)

Anonymous Coward | more than 2 years ago | (#37006850)


Heuristic Algorithm (1)

Len (89493) | more than 2 years ago | (#37006930)

Examination of the example in the article suggests a heuristic algorithm that should provide near-optimal solutions and is suitable for real-time execution on neural wetware.

1. Start by mowing around the outside border.
2. Proceed going around, from the outside in.
3. When you reach a strip <= 3 mowers wide, clear it with short back-and-forths.

Proof of an upper bound on excess mowing vis-a-vis the optimal solution is left as an exercise for the reader.

Solution is WRONG. Look at it. (0)

Anonymous Coward | more than 2 years ago | (#37006946)

I think that the math is now fine but you can see that the answer is clearly wrong by looking at the result.

Look how close to the edges you have to drive. Almost half of the lawn mower will be out of the green area. And that goes around the outer perimeter of the whole area. That just can't be simply optimal way to do it even if it produces a nice grid incide of the area.

Its simple really... (1)

armer (533337) | more than 2 years ago | (#37006952)

1. Buy beer. 2. Start mower. 3. Open beer. 4. Start "mowing and drinking" 5. Be amazed as time flies and the grass gets cut
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account