Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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.


share|improve this question
Now posted to MO, mathoverflow.net/questions/89083/mathematics-of-rectangles, without notifying either site of the post to the other. –  Gerry Myerson Feb 21 '12 at 5:06
what the problem about that? –  Hassan Feb 21 '12 at 5:48
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. –  Gerry Myerson Feb 21 '12 at 10:18
ok good point: optimizing getting a response –  Hassan Feb 21 '12 at 11:21
add comment

1 Answer

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

share|improve this answer
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) –  Hassan Jun 6 '12 at 15:50
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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