Quickly locating nearest rectangle from a point

Question

The problem is as follows:

There are several rectangles in the plane (they are not necessarily axis-aligned), how can we index them in such a way that given a point $p$ we can quickly locate the nearest rectangle from $p$? The distance from a point $p$ to a rectangle $R$ is defined as the Euclidean distance between $p$ and its nearest counterpart $q \in R$. If $p$ is inside the rectangle, then the distance is $0$.

Actually what I want is the distance between $p$ and its nearest rectangle, so if we can directly get this distance, it's even better.

The naive solution is to compute the distance between $p$ and each rectangle, however this is time consuming in my case, so I want to know if there exists such a data structure.

Edit:

These rectangles may intersect, and the total number is very likely less than 20 (typically around 5). It is trivial if we only want to know this minimal distance for a few points, linear scan will do the work. However when the number of such points becomes very large, the overall computation overhead cannot be ignored, that's why I want to quickly find the nearest rectangle.

Answer 1

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

Answer 2

Here's another approach:

The rectangles basically form a generalized Voronoi diagram where the seeds are rectangles instead of points. Each cell in this diagram forms a polygon. The algorithm for computing these polygons is basically the same as that of the regular Voronoi diagram: compute the boundary cutting the plane in to two half-spaces for each pair of rectangles, and intersect the resulting half-spaces over all pairs to find the correct polygon. The polygons (unfortunately) are not necessarily convex, but you can split each polygon into a set of convex polygons

Once you have this list of convex polygons, partitioning the plane, each mapping to a rectangle, all you have to do for a given point is to find which polygon it's in. This can be done by computing the dot product for each side of the polygon, to find which side of the line it's on.

If you do this straightforwardly, you end up with $O(nm)$ dot product computations for $n$ polygons with $m$ sides each, which is probably not better than computing the distance to the rectangles normally. However, each test for the point against a line segment basically eliminates all polygons on one side of the line. You can use this to find a binary tree where each node represents a choice of line segment in the diagram against which you compute the dot product, and the leaves contain a ginle polygon. This suggests that if you have $n$ convex polygons, you can decide the correct polygon in $\log_2 n$ computations of a single inproduct. I expect this will be efficient, but you might be unlucky and get lots of non-convex polygons that have to be split into many convex ones.

It's quite a job to work all this out into an actual algorithm, and I'm sure I've overlooked some things, but the literature on generalized Voronoi diagrams seems to be quite extensive, so with a little reading you should be able to work it out (if the speedup is worth the effort).