Quickly locating nearest rectangle from a point
I expect the best option is to use some kind of spatial index. Here's a first suggestion, but I'm sure there are better solutions.


Create a quad tree with a maximum bucket capacity of $m$.
For each new rectangle, traverse the tree, and store a pointer to the rectangle at each bucket that intersects the rectangle.


Now to find the nearest rectangle for a point $p$:


Find the bucket $B$ the point falls in.
Find the distance $d$ to the nearest rectangle $B$.
Check all surrounding buckets for rectangles that might be closer than $d$.


The last step might still be expensive if you're unlucky, but you can effectively eliminate all buckets that are itself further from $p$ than $d$.