I have set of rectangles of various sizes in 2D space. Number of rectangles may be changed dynamically from 10 to 100 000, their position, as well as their sizes are often updated.
Which spatial structure would you recommend to find rectangle at given point (x,y)? Assuming that search operation also performed very often (on mouse move for example). If you could give a reference to various spatial indexing algorithms comparison or compare their search/build/update performance here - that would be lovely.
I would suggest R-Tree. It is primarily designed for rectangles (or N-dimensional axis aligned cubes).