3
$\begingroup$

I am struggling with a fairly simple and natural geometric optimization problem, but I have not been able to find an obvious canonical method for solving it:

I am given a collection of $m$ axis-aligned rectangles in the unit square, and my goal is to find the optimal positions of a set of $k$ distinct axis-aligned rectangles with given dimensions such that none of the $m+k$ rectangles intersect, and the sum of distances between the centers of the $k$ rectangles are minimized. Distances between rectangles are measured with respect to the length of the shortest $L_1$ path that does not intersect another rectangle (so it's often larger than standard $L_1$ distance).

Is there a field of optimization or computational geometry that would deal with this? I don't even see an obvious way to formulate it as a mixed integer linear program, due to the presence of shortest paths.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Are your rectangle sides aligned with the surrounding unit square, or are they oriented arbitrarily? $\endgroup$
    – Joseph O'Rourke
    Commented Feb 27, 2017 at 22:15
  • 1
    $\begingroup$ Why not place $k$ tiny squares in some little gap. The sum of the distances between those rectangles can be as small as desired. I must not understand the problem correctly... $\endgroup$
    – Joseph O'Rourke
    Commented Feb 27, 2017 at 22:17
  • 1
    $\begingroup$ Thanks @JosephO'Rourke, I'll clarify. Everything is axis-aligned, but the $k$ rectangles have given dimensions. $\endgroup$
    – Tom Solberg
    Commented Feb 27, 2017 at 22:19
  • 1
    $\begingroup$ This is close to what is known as the labeling problem. Here is a chapter by K.Kakoulis & I.Tollis that might help: PDF download. Most versions are NP-hard. $\endgroup$
    – Joseph O'Rourke
    Commented Feb 27, 2017 at 22:30
  • $\begingroup$ maybe not unrelated: the problem of "Squaring the Square", which is partitioning a square into a set of unequal squares. There is a chapter in Bollobas book "Modern Graph Theory". What is interesting, is the relation to electrical networks, which may be worth considering in your problem. $\endgroup$
    – Manfred Weis
    Commented Feb 28, 2017 at 5:54

0

Reset to default

You must log in to answer this question.