Under this answer, user Bruno Joyal asks:

This might be a naive question, but... how do we know there is a best possible solution?

I (but that's just me) assume that he might be thinking of a logical possibility that there is a sequence of ever better solutions, but that the limit itself is not a solution. But, whether he is or not doesn't quite matter. So, here goes...

Can it be proven that there exists an optimal solution?

How big a square do you need to hold eleven little squares?

enter image description here

We don't even know if this is the best possible [solution.]



The configuration space can be represented as a compact set, specifying for each square the position of one corner and the angle of rotation, as well as the size of the big square (which can be assumed to be bounded by some ridiculously large constant). The constraints are all of the form $f(\omega) \ge c$ where $\omega$ is the configuration and $f$ is a continuous function, and the objective (the size of the big square) is a continuous function. So yes, the minimum does exist.

  • 3
    $\begingroup$ Is it obvious that the configuration space is compact? Seems like this is really the heart of the question. $\endgroup$ Nov 26 '13 at 18:47
  • 2
    $\begingroup$ Yes, $[0,R]^n \times [0,2\pi]^n$ is compact. $\endgroup$ Nov 26 '13 at 19:07
  • 3
    $\begingroup$ As for the constraints, note that the area of overlap of two squares is a continuous function of the configuration. $\endgroup$ Nov 26 '13 at 19:17
  • $\begingroup$ Thanks! When I said "configuration space", I meant the subset where the constraints of the problem are satisfied. I am convinced now! $\endgroup$ Nov 26 '13 at 19:31
  • $\begingroup$ @BrunoJoyal Good enough for me (although it did require some thinking of my own). If you concur, I'll accept this answer. [Edit: I missed your last comment. I'll accept.] $\endgroup$
    – Řídící
    Nov 26 '13 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.