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.

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

1 Answer 1

1
$\begingroup$

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

$\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.