Reduce distance computation overhead between a point and several rectangles We are given several rectangles in the plane, without loss of generality, assume there are three of them, namely $R_1$, $R_2$ and $R_3$.
For a point $P$, we can compute three distances $d_1$, $d_2$ and $d_3$ between $P$ and each rectangle respectively, and a final distance $d_{min}$ is defined as $d_{min}=\min (d_1,d_2,d_3)$.
There are $n$ such points randomly scattered in the plane, and we want to know $d_{min}$ for every point. The naive solution would require $3n$ distance computations.
I'm wondering whether we can do some preprocess to $R_1$, $R_2$ and $R_3$ to reduce the number of distance computation. Or, put it another way, can we compute $d_{min}$ directly according to some aggregated information of $R_1$, $R_2$ and $R_3$, instead of computing $d_1$, $d_2$ and $d_3$ at first?


If the rectangles are not too many, you can store the Voronoi diagram of your configuration in a convenient way (as a set of linear and quadratic inequalities, for instance), then find, for each point $P$, the index $i$ of the region where it belongs, in order to compute only $d(P,R_i)$.
