I am learning about the science of algorithms and I'm studying some problems with their optimum algorithm. The problem I describe below is one of them.
I need a lower and an upper bound of its runtime complexity. What is its optimum algorithm? I don't need any implementation.
Problem:
Given a set of coordinates in a $2$-dimensional plane, how do we find the area of a minimum square which includes all the points? The points can exist on the border also. And the square's orientation doesn't have to be parallel to the Cartesian axes.
For example,
Consider the points $(-1,1)$, $(1,3)$, $(0,2)$, $(-2,2)$. The minimum square height to cover these points is $2\sqrt{2}$. Hence the area is $8$.
I hope that the explanation is clear. Thank you in advance!
Edit:
The lemma below is false, as per @BrianTung 's comment.
The question is interesting even for a triangle. There you can prove that at least one vertex must be a vertex of the minimal containing square, and that for an obtuse triangle the square whose diagonal is the longest side does the job. For more on the triangle problem, see
Smallest square containing a given triangle.
Everything from here on is deprecated.
Thoughts toward an answer, modulo a lemma.
(That's known for the minimal bounding rectangle.)
So find the convex hull, in time $O(n \log n)$. (https://en.wikipedia.org/wiki/Convex_hull_algorithms) Then loop on each of the at most $n$ edges of the convex hull, finding the minimal bounding square containing that edge, in time at most $n$.
That would be an $O(n^2 + n \log n) = O(n^2)$ algorithm, possibly even faster.
See http://www.uni-kiel.de/psychologie/rexrepos/posts/diagBounding.html for R code.