9
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\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$
    – Marcelo Fornet
    Dec 31, 2019 at 17:47
  • $\begingroup$ Yes, that is correct. $\endgroup$
    – taktoa
    Dec 31, 2019 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$
    – Marcelo Fornet
    Dec 31, 2019 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$
    – Marcelo Fornet
    Dec 31, 2019 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, 2020 at 1:47

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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