Minimum Perimeter Triangle

Sort the points by their $x$-coordinates and apply divide and conquer.

Split the current set into a left half and a right half, and recursively compute the minimum perimeter in each half. Let $\delta$ be the smaller of the two answers. It remains to check whether a triangle using points from both halves has perimeter smaller than $\delta$.

Every side of a triangle whose perimeter is smaller than $\delta$ has length smaller than $\frac{\delta}{2}$. If the side lengths are $a,b,c$, the three points are not collinear, so

$$a<b+c.$$

Thus,

$$2a<a+b+c<\delta.$$

Consider a triangle using points from both halves. Two vertices from different halves are less than $\frac{\delta}{2}$ apart, so every vertex lies in the vertical strip whose horizontal distance from the dividing line is less than $\frac{\delta}{2}$. Since every side is shorter than , the range of the three -coordinates is also smaller than .

Therefore, sort the points in the strip by $y$-coordinate and only consider points whose $y$-coordinate difference is smaller than $\frac{\delta}{2}$.

Only a constant number of points can lie in such a range. Consider any horizontal portion of the strip of height $\frac{\delta}{2}$. The parts to the left and right of the dividing line are rectangles of width and height at most $\frac{\delta}{2}$.

Divide each rectangle into $2$ columns and $3$ rows. Each small rectangle has width $\frac{\delta}{4}$ and height $\frac{\delta}{6}$, so its diagonal is

$$\sqrt{\left(\frac{\delta}{4}\right)^2+\left(\frac{\delta}{6}\right)^2} = \frac{\sqrt{13}}{12}\delta.$$

If one small rectangle contained three points from the same recursive half, those points would form a triangle of perimeter at most

$$3\cdot\frac{\sqrt{13}}{12}\delta = \frac{\sqrt{13}}4\delta <\delta,$$

contradicting the recursive answer for that half.

Hence each small rectangle contains at most two points. There are $6$ small rectangles on each side, so at most $12$ points lie on each side and at most $24$ points lie in total.

Thus, while scanning the strip in $y$-order, it is sufficient to try every triangle formed by each point and the constant number of following points. Triangles whose three vertices belong to the same recursive half have already been handled recursively and may be skipped.

Before evaluating a perimeter, the implementation first checks whether all three squared side lengths are smaller than $\left(\frac{\delta}{2}\right)^2$. Square roots are computed only for triples passing this filter, which significantly improves the constant factor.

At every recursion level, the two lists sorted by $y$ are merged in linear time. Therefore, the total time complexity is

$$O(N\log N),$$

and the memory complexity is $O(N)$.

Solution written by GPT5.6