7
$\begingroup$

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!

$\endgroup$
3
  • 2
    $\begingroup$ You probably want to start by calculating the convex hull (there are algorithms for that). Finding a rectangle is known: en.wikipedia.org/wiki/Minimum_bounding_box_algorithms $\endgroup$
    – Ethan Bolker
    Commented Dec 29, 2015 at 14:58
  • $\begingroup$ I thought a bit and I think I found an $O(n^3)$ algorithm. Think about how many points from the original set lie on the border of the square. $\endgroup$
    – Element118
    Commented Dec 29, 2015 at 15:24
  • $\begingroup$ Element118, you think that three points lie on the border at least no? $\endgroup$
    – Tive Surrender
    Commented Dec 29, 2015 at 15:33

1 Answer 1

Reset to default
1
$\begingroup$

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.

An edge of the minimal area square will contain an edge of the convex hull.

(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.

$\endgroup$
3
  • $\begingroup$ Given that it's true for the minimal bounding rectangle, I don't see that it follows for the minimal bounding square. Imagine four points that are the corners of an extremely long rectangle (with respect to its width). The minimal bounding rectangle is obviously just the convex hull of those four points. But the minimal bounding square will have that rectangle aligned along the square's diagonal. $\endgroup$
    – Brian Tung
    Commented Dec 29, 2015 at 17:56
  • $\begingroup$ @BrianTung You're right, of course. The convex hull may help, but not in an obvious way. I may delete my (non)answer. $\endgroup$
    – Ethan Bolker
    Commented Dec 29, 2015 at 20:02
  • $\begingroup$ Perhaps not yet. So long as it is explicitly incomplete, it may help someone else formulate a more complete answer. $\endgroup$
    – Brian Tung
    Commented Dec 29, 2015 at 21:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .