I was trying to implement data structure over set of rectangles that can perform two types of operations.

  1. Update operation, add new rectangle with sides parallel to x and y axis and positive coordinates to the set.

  2. Query operation, for some rectangle check if there is some rectangle intersecting with this rectangle.

I don't have big knowledge of data structures so I was thinking if you could give me some hints how to start approach this problem.

Thanks in advance.

  • 1
    $\begingroup$ This seems to be non-trivial even in the one dimensional case $\endgroup$ – DreamConspiracy Dec 7 '18 at 18:31

You might want to look into R-trees (described in detail here) or a similar tree data structure for spatial indexing.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.