Quote:>One of the easiest and in some cases the fastest solution is to maintain

>two sorted lists of coordinates, one for the endpoints of the x-projections

>of the rectangles and one for the y-projections. [..]

>There you have it, in expected linear time.

While I don't question the merits of this approach, I'm not sure that it's

the best solution to the problem. I think that the original poster was

after an algorithm that finds all rectangles overlapping *one* query

rectangle. That can of course trivially be done in linear time by just

testing all rectangles. So "efficient" for this problem would be

logarithmic time, which you achieve with a multidimensional search tree.

The above sounds like an algoritm for finding *all* overlaps in a set

of rectangles.

Quote:>The algorithms described in computational geometry literature which are

>based on trees of interval trees are monsters to update in case of moving

>rectangles, so I would not recommend using them.

Moving rectangles in an n-D tree probably means deleting and re-inserting

nodes. While insertion is trivial and well treated in the text books,

deletion is indeed much more difficult. I do it by removing the whole

partial tree* below the node to delete, and re-inserting all of

these nodes. While this sounds costly, it's relatively simple, it works,

and it's efficient enough for my purpose. Since a tree naturally has

the property that most nodes are close to the leaves, the partial tree

is normally small.

--