1. I'm looking for all stuff relative to Rectangles Set (specialty rectangles with edges parallel to axes of orthonormal 2d space: lets note it $RS$. I found this interesting article A new tractable subclass of the rectangle algebra. Does anyone knows other works?

  2. Given a set $S$ of rectangles in $RS$ , and a point $P$ in the same space, how can I find the "nearest" rectangle, with given height and width , to the point $P$ such that it do not "overlap" any element of $S$.

    • nearest means: in the sense of the distance between the "center" of the rectangle and the point P
    • center of rectangle means: the point with coordinate the center of each interval that defines the rectangle.
    • overlap: means that the set of points defined by the two rectangles intersect.


  • 3
    $\begingroup$ Now posted to MO, mathoverflow.net/questions/89083/mathematics-of-rectangles, without notifying either site of the post to the other. $\endgroup$ Commented Feb 21, 2012 at 5:06
  • $\begingroup$ what the problem about that? $\endgroup$
    – Hassan
    Commented Feb 21, 2012 at 5:48
  • 7
    $\begingroup$ You are asking people for help. The least you can do is to let them know what you know about the problem, including where else you have asked it, so they don't waste their time duplicating what others are doing. Heck, it also helps you, as people at one site may see something at the other that gives them an idea they wouldn't have had otherwise. But, really, it's common courtesy. $\endgroup$ Commented Feb 21, 2012 at 10:18
  • $\begingroup$ ok good point: optimizing getting a response $\endgroup$
    – Hassan
    Commented Feb 21, 2012 at 11:21

1 Answer 1


I can't help you for the first question, but I'll answer the second question.

Instead of looking for rectangles, since your height and width are fixed, you can simply look for center points. The set of feasible centers is: $$C=\mathbb R^2 \setminus \bigcup S'$$ where $$S' = \left\{ (a-w/2,b+w/2)\times(c-h/2,d+h/2)\ :\ (a,b)\times (c,d)\in S \right\}$$ Then you are looking for $c\in C$ minimizing $\|c\|$ (we can assume without loss of generality that you want a center as close to (0,0) as possible).

This already gives a polynomial time algorithm, as the complementary and union of overlapping rectangles can be done in polynomial time, and once this is done you can find $c$ in linear time.

If you want a more efficient algorithm, you can sort the rectangles in $S'=\{s_1,\dots,s_n\}$ so that $\|s_1\|\le\dots\le\|s_n\|$ (letting $\|s\|=\inf\limits_{x\in s} \|x\|$, computable in $O(1)$ time).

Then you can progressively compute $C_i=\bigcap_{j=1}^i \mathbb R^2\setminus s_j$, which you represent as a finite union of rectangles $R_i$. Define $\|C_i\|=\min_{r\in R_i} \|r\|$. As soon as you find an $i\ge 1$ such that $\|C_i\|\le\|s_{i+1}\|$, you can stop and $c$ is any point in $C_i$ achieving $\|c\|=\|C_i\|$.

You now have an algorithm polynomial in the number of rectangles in $S'$ intersecting the disk of radius $\|c\|$ centered in 0, and linear in the total number of rectangles (by using a priority queue).

  • $\begingroup$ thanks Generic Human, i was expecting a slution that utilise a kind of space of Rectable with some norm ... and utilise the exact method of other one in optimization theory (i ll let the bandary for who answore the first question , the system will give it to you automaticaly if no one answer i think) $\endgroup$
    – Hassan
    Commented Jun 6, 2012 at 15:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .