2

Maximize area in $1000\times 1000$ array using two non-overlapping squares centered at two points, p1 and p2. The following conditions must be met:

  1. The area (square 1 area + square 2 area) should be a maximum for the given points, p1 and p2
  2. The squares must be centered on their respective point (i.e. must have area $n^2$, where n is odd)
  3. The squares cannot overlap
  4. The squares must remain within the $1000\times 1000$ grid

Note: The squares do not need to be the same size.

I solved the equivalent 1D case, but the 2D case seems quite a bit more challenging. Has anyone solved this before, or have any suggestions/ideas for solving such a problem?

This is my first post on here, so let me know if I'm doing it wrong... Thanks!

Thomas Andrews
  • 177,126
Francis
  • 33
  • What is the source of this problem? –  Feb 05 '15 at 02:34
  • I thought this problem up when analyzing two separate regions on a 2D camera array in matlab. I couldn't find any reference to this "constrained bin-packing" problem, so I thought I'd ask here. Thanks for you interest. – Francis Feb 05 '15 at 02:59

1 Answers1

1

Some thoughts:

  1. obviously if the points are closer to the edge than they are to each other, then the maximum will involve both squares touching the edge.
  2. otherwise, the two squares will have a total edge length equal to twice their centers' maximum axis distance apart: Two points that are 300 distance apart can be 599x599 and 1x1, or 299x299 and 301x301, or some other combination that sums the same way.

If their distance apart is $d$, and the edge length of one square is $x$, then we have: $z=2d-x$, and the total area is $x^2+z^2=x^2+4d^2-4xd+x^2=4d^2-4xd+2x^2$.

Since $d$ is held constant, we have an upward-pointing parabola. Thus, the farther we can get from the vertex, the better. So where's the vertex?

Well, it's at $-b/2a=4d/4=d$. So the lowest area is when the two squares are equal in size!

Thus, the highest area picks the largest square we can fit around one of the points without either 1. leaving the area or 2. overlapping the other point. Pick the point that gives the larger of these to put the large square around, and you win.

Dan Uznanski
  • 11,025