# Area of the union of rectangles anchored on the x-axis

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.

1. What is (an upper bound on) the combinatorial complexity of the union $K$ of the rectangles in $S$?
2. 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?

• What is the complexity of your approach? I can think of an $O(n\log n)$ solution. – Syzygy May 23 '12 at 12:13
• @VinayakPathak, thank you very much for the comments. You described exactly the worst case scenario and it's time complexity is $O(nlogn)$. Thanks for the definition of combinatorial complexity – com May 23 '12 at 18:31
• @com: There isn't just one "sweepline algorithm". What information do you need to maintain about the intersection of the sweepline and the rectangles? (Hint: It's not the complete sorted list of intersection points.) What data structure efficiently maintains that information as things are inserted and deleted? (Hint: It's not a "queue" or a "tree".) Also, Vinayak's comment is incorrect — When the sweepline reaches the right edge of rectangle $i$, you must delete rectangle $i$ from the data structure. There is nothing to decide. – JeffE May 24 '12 at 8:21