Problem of the Week 1207

A Long Greedy Cycle

A "greedy cycle" through a set of points is the cyclic route a traveling salesman would take if he starts at one of the points and, at each move, visits the nearest unvisited point, returning to the start at the end to close the cycle.

Find six points in the unit square so that the greedy cycle from one of the points that passes through all the points has length at least 5.25. Try to get the length as large as possible.

Source: Larry Carter and Adam Chalcroft.

[View the solution]