Strawberry Fields (ITA Archived Puzzle, Analyzed)

Please refer to the strawberry fields problem on this page

Analysis

Think of each strawberry as a point on an XY plane. Then we can find out the concave hull which is the smallest polygon that contains all the ponits or strawberries.

Assume for some given strawberry field, the concave hull is something like this

---

Now walk through the vertices of the concave hull in succsession. For each pair of successive vertexes, find the point of intersection that is outside the concave hull. This will now result in an updated polygon as shown.

---

Finally pick the largest edge and from the two edges, one of which succeeds the largest edge and the other which precedes it, pick the larger one. Form a rectangle between the largest edge and the selected succeessive or preceding edge. This is depicted here.

---

Now choose all points of the concave polygon that lie outside the rectangle that we just derived. Add to this set of points, a point that would have been derived as a result of deriving the rectangle. Repeat the process of forming the rectangle till all points of concave polygon are covered. For the sample, the final result is shown.

---

Algorithm

The steps of the algorithm are enumerated below.

• Assuming the lowest row of the starwberry field as the X axis and the left most column as the Y axis, read the starwberries as points on XY plane.
• Find out the concave hull of the strawberry points.
• For the largest edge of the concave hull, pair it with the larger of the edge that succeeds or precedes it. Build a rectangle from this pair. Add a point that might have been generated as a part of building the rectangle to the set of points S of the concave hull that lie outside the built rectangle.
• Repeate the process in the previous step for the set of points S of the concave hull that are yet to be covered till no more points remain.