I have a large set of rectangles with random orientation and size. Say up to $10000$ rectangles, which are non-overlapping.
For every rectangle, I need to find the nearest compatible neighbor. Two rectangles are said to be compatible when the angle they both form with the line that joins their center is below a fixed tolerance. The distance is computed between the rectangle centers. Note that every rectangle has two orthogonal directions. (In a more advanced version of the problem, the tolerance can also depend on the sizes.)
I can obviously solve this by exhaustive search, trying all pairs of rectangles, but this is an $O(N^2)$ process. I am looking for algorithmic ways to accelerate (parallelization is not an option). I know about efficient solutions for the all-nearest-neighbors search based on the Voronoi diagram, kD-trees and similar techniques, but in my case the compatibility condition makes them unsuitable.
Any suggestion ? A speedup factor of $10$ would already be very welcome.