# Mathematics of Rectangles

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.

regards

• 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

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