I am trying to solve the following computational geometry problem.
Let $S$ be a set of $n$ axis-parallel rectangles in the plane, so that the bottom edge of each rectangle in $S$ lies on the $x$-axis.
- What is (an upper bound on) the combinatorial complexity of the union $K$ of the rectangles in $S$?
- Give an efficient algorithm for computing the union and its area.
I suggest using sweep line algorithm for the purpose of computing union of areas. First we should consider queue of events. Events are just the leftmost and the rightmost $x$'s of rectangle. As in standard interpretation all $x$'s should be sorted.
Start iterations on event queue (like in standard algorithm). On every new event we can compute an area we've already covered. When two or more rectangles intersect (can be identified by data structure) we should pick the rectangle with the biggest $y$-coordinate until the next event.
That's a general idea. The main difference from the classic sweep line algorithm is that we don't have to compute intersection and inserting them to queue. All we are interested in is intersection of rectangles which occur on vertical lines of leftmost $x$ and rightmost $x$.
I am not completely sure that the solution I presented is the correct one. This exercice was marked with high complexity grade. Maybe I missed something?
In addition, I don't know how to answer the first question.