Problem: Given n points in x - y plane, it is required to find the minimum area for a square that encloses all the points.

For sure, some points will lie on the square sides in the optimal solution. I found a solution that finds the convex hull for the points. Then for each vertex, we will assume it is on the boundary, so, we will try to find the best rotation for the square. The rotation angle interval is determined by the angle at this vertex, so that the interval limits produce squares with sides overlapping with the two polygon sides intersecting at this vertex.

The solution finds the the best rotation angle for each vertex using ternary search. I am not sure why the area of a square for a fixed vertex is a unimodal function. Can someone prove it?