Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $\{(w_i, h_i, x_i) \mid i \in \{0, \ldots, n - 1\}\}$, as well as a bound $(y_\mathrm{min}, y_\mathrm{max})$ on the valid y-positions. These rectangles must have integer-valued coordinates for their vertices. Is there an efficient (e.g.: $O(n^3)$) approximation algorithm that gives a sequence $\{y_0, \ldots, y_{n - 1}\}$ of y-positions such that the number of overlaps between any two rectangles (i.e.: edges in the overlap graph) is minimized (and hopefully zero)?

Note that if $y_\mathrm{max} = 10$ and $h_k = 3$, then $y_k = 9$ would be invalid, since the top edge would be at $12$ which is more than $10$.

  • $\begingroup$ Just to be sure, if we have $w_i$ and $x_i$ we can safely assume we know for each rectangle its projection into the $x$ axis to be $[x_i, x_i + w_i]$. So we only need to choose for every rectangle the $y_i$ coordinate of its lower edge. Is that correct? $\endgroup$ Dec 31 '19 at 17:47
  • $\begingroup$ Yes, that is correct. $\endgroup$
    – taktoa
    Dec 31 '19 at 18:00
  • $\begingroup$ It reminds me to a very difficult problem which can be seen as a 1D version of this problem. Check it here. This was the hardest problem in the ICPC World Final competition (so you can assume it was very hard). Check the editorial (problem H). Your problem can be reduced to this problem (for the zero overlapping case). They quote this paper “Scheduling Unit-time Tasks With Arbitrary Release Times and Deadlines” by Garey, Johnson, Simons, and Tarjan (SICOMP, 1981). $\endgroup$ Dec 31 '19 at 18:09
  • $\begingroup$ Ohh, I missed something important from your problem, $[y_{min}, y_{max}]$ is fixed for all rectangles. Disregard previous message, I'll leave it in case the quoted paper helps you somehow, but it is not the same problem. $\endgroup$ Dec 31 '19 at 18:15
  • 1
    $\begingroup$ I think in graph theoretic terms this is a variant of $T$-coloring problem in interval graphs, and maybe related to the frequency assignment problem. $\endgroup$
    – Laakeri
    Jan 2 '20 at 1:47

This is called the offline dynamic storage allocation problem. Check out the papers cited by https://epubs.siam.org/doi/abs/10.1137/S0097539703423941 for a good review of the literature.


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.