Communications of the ACM

Last byte

Randomower

By Dennis Shasha
Communications of the ACM, October 2021, Vol. 64 No. 10, Pages 96-ff
10.1145/3477385
Comments

There is one perfectly flexible but unbreakable rope attached to two posts on a large but unkempt lawn. The posts are 1,000 meters apart and the rope is 1,100 meters long. So there is some slack in the rope.

A randomower is a driverless lawn-mower that moves randomly and is able to change direction by an arbitrary angle at any time. Fortunately, it can be clipped to the rope so it will not wander off too far. You are trying to use this random lawnmower to cut at least part of the grass between the posts. Let the rope's zero point be at post A and its end point (1,100 meters away along the rope) at post B.

Suppose you wanted to cut the grass to clear a path, that is, a line segment at least the width of the lawnmower itself, between the two posts. It is OK if more grass is cut to the side of the path, but you want to ensure you have a straight continuous path. The first challenge is to do this with the minimum number of attachments.

Warm-up: What is the smallest number of attachments necessary to mow a straight line segment (and, optionally, other grass) from post to post?

Solution to Warm-Up: Attach the randomower to the 100-meter mark along the rope starting say from post A. Because the rope is 100 meters longer than the distance between the posts, the distance along the rope between the attachment point of the randomower and post B is 1,000 meters. Therefore, the randomower can reach post A up to a point 100 meters from post A in the direction of B. Next, attach the randomower at the 200-meter mark along the rope from post A. Keep going for 300, 400, … 1,000. So, all together we will need 10 attachments.

Figure. What is the maximum area this randomly moving lawnmower (randomower) can mow, while staying attached at a single point on the rope?

Now, let's reset the lawn to its unkempt state and ask a few other questions. If we were to attach the randomower to a single point along the rope, where should we attach it to cut the greatest area of grass? It might seem that near an end might be best, though symmetry suggests the middle.

Warm-up 2: Given some attachment point p = 400 meters from post A, what would be the maximum width of the mowed area?

Solution to Warm-up 2: If p = 400, we have a triangle of length p = 400, 1,100-p, and 1,000. This gives us an interior angle of 0.31756 rad (thank you, Wolfram Alpha). So the width will be 700 ^* sin 0.31756 = 218. That is just one side, so we must double this to get the total width. Notice this is a lot more than 99.8 meters, which is what we would get by attaching to p = 100.

So, now we can ask where would be the best place to attach randomower to achieve the largest area.

Challenge: What would be the area of the mowed grass if you attached the randomower to the 550-meter point along the rope?

Solution: Denote by Pup and Pdown the most extreme points on either side of the line segment between A and B when attaching randomower to the 550-meter point along the rope. To compute the area, we must consider the pie-shaped area defined by A and the arc from Pup to Pdown and subtract from that the area of the triangle defined by A, Pup, and Pdown. Then we do the same thing starting from B.

Suppose randomower is attached at 550 meters along the rope. Let point P be the point exactly between A and B. Consider the right triangle defined by post A, point P, and point Pup. The distance from P to Pup is sqrt((550²) - (500²)) or 50 ^* sqrt(21) on each side of the line segment, which is approximately 229.

The area of the triangle P, Pup, A is 57,282. This must be doubled because we must add in the triangle Pdown, Pup, A. The doubled area is 114,564.

The arc defined by A, Pup, and Pdown has a radius of 550 and an interior angle of 0.86 radians. So the area of the pie described by this portion of the circle is (550²) ^* 0.86/2 = 130,140 square meters. The difference of the pie area (130,140) and the triangle area (114,564) is 15,576 square meters. Double this because of the similar arc anchored at post B. End of solution.

Given this geometrical intuition, you are now prepared for Upstarts.

Upstart 1: If there are k attachments available, where should you put them to mow the greatest amount of area?

Upstart 2: How many attachments are needed to draw a segment of width w for some w less than 70 and where should those attachments be placed?

Upstart 3: Suppose A and B play a game in which each wants to use attachments that cut as much of the lawn as possible. They take turns as follows: A makes the first attachment. Then B makes two. Then A makes two. This goes on until each makes the same number of moves (A determines when to make last move by making a single attachment). Each player gets credit for every part of the lawn that is first mowed by randomower due to an attachment by that player. Please find a winning strategy for some player.

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2021 ACM, Inc.

---

No entries found