0
$\begingroup$

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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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