0
$\begingroup$

Given a set of $n$ rectangles $[a, b] × [c, d]$ in a cartesian coordinate plane, calculate the area of their union.

My first thought of this problem is by using a simple sweep line algorithm plus a segment tree. However i could not get any idea to design such a segment tree that works. Any idea?

I also have another version of this problem, that is to find the area of all regions that are covered by exactly $k$ rectangles.

$\endgroup$
3
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$ Commented Aug 6 at 8:06
  • $\begingroup$ The question is perfectly clear ! See the accepted answer to this question. $\endgroup$ Commented Aug 6 at 8:10
  • 1
    $\begingroup$ Thank you for the reference to the solution. This question had haunted me in the past and I always doubted that a sweep line algorithm and a segment tree will work, but i never found one solution myself, and I couldn't find any solution on the internet. $\endgroup$ Commented Aug 6 at 8:18

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.