Editorial

Tour

Editorial

Compute the convex hull of all points and let its area be $A$ .

If the convex hull is a segment, sort the points lexicographically by $(X_i,Y_i)$ and output that order. Now suppose the convex hull has positive area.

Set the strip spacing to $h=\sqrt{\frac{2A}{N}}$ and let . Use the following two horizontal grids: and , where is an integer.

For each grid, build one candidate tour as follows.

Assign every point to its nearest grid line.
Process the grid lines from bottom to top. If the grid-line index $k$ is even, visit the assigned points in increasing order of $X$ ; if it is odd, visit them in decreasing order of $X$ .
Connect the last point back to the first point.

Compute the lengths of the two candidate tours and output the shorter one. The convex hull and its area can be computed in $O(N\log N)$ time, so the whole algorithm runs in $O(N\log N)$ time.

Proof

Let $W$ , $P$ , and $D$ be the horizontal width, perimeter, and diameter of the convex hull. We have $W\le D$ .

Fix one grid. Project every point vertically onto its assigned horizontal line. Expand the convex hull upward and downward by $\frac{h}{2}$ . Every projected point lies inside the expanded convex body. Its area is , its perimeter is , and its diameter is at most .

Solution written by GPT5.6

Y_{\min}=\min_iY_i

Y=Y_{\min}+kh

Y=Y_{\min}+(k+\frac12)h

k

2h

A+hW

P+2h

D+h

Imagine traversing every horizontal segment obtained by intersecting the expanded body with a grid line. Move from bottom to top, traversing one segment from left to right and the next from right to left. Connect the endpoints of consecutive segments on the same side by a straight segment. Such a segment is no longer than the corresponding boundary arc of the convex body. Therefore, the total cost of connecting consecutive horizontal segments is at most $P+2h$ , and closing the walk costs at most $D+h$ .

Whenever the walk reaches a projected point, make a round trip to the original point. After all points have been visited, shortcut auxiliary points using the triangle inequality. The tour produced by the algorithm is no longer than this auxiliary walk.

The two grids are shifted by $\frac{h}{2}$ . For every point, the sum of its distances to the nearest line of the first grid and the nearest line of the second grid is $\frac{h}{2}$ . Hence the average round-trip cost from the grid lines to the original points is $\frac{Nh}{2}$ over the two candidates.

Let $f(y)$ be the horizontal cross-section length of the expanded convex body at height $y$ . The union of the two grids is a grid with spacing $\frac{h}{2}$ . By convexity, $f(y)$ first increases and then decreases, so its total variation is at most $2W$ . Bounding the difference between the Riemann sum on this grid and the integral by the total variation shows that the average horizontal movement of the two candidates is at most $\frac{A}{h}+2W$ .

Therefore, one of the two candidates has length $L$ satisfying

L\le \frac{A}{h}+\frac{Nh}{2}+2W+P+D+3h.

Since $h=\sqrt{\frac{2A}{N}}$ , the first two terms sum to $\sqrt{2AN}$ . For a planar convex body of diameter $D$ , we have $A\le\frac{\pi D^2}{4}$ , $W\le D$ , and $P\le\pi D$ . Also, $N\ge3$ gives $3h\le3D\sqrt{\frac{\pi}{6}}$ . Thus

L\le D\sqrt{\frac{\pi N}{2}}+\left(\pi+3+3\sqrt{\frac{\pi}{6}}\right)D<D\left(\sqrt{\frac{\pi N}{2}}+10\right).

If the convex hull is a segment, the lexicographic order gives a tour of length at most $2D$ , so the same bound holds.

<