Mathematics of Rectangles 
*

*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?

*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
 A: 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).
