Efficient unions and intersections in 2D plane when y_min = 0
I tried to write the whole thing out in psudo-code, and found that it was too psudo-y to be useful and too code-y to be readable. Here's the basic idea:
You can sort each of your input lists in O(n*log(n)). 
Because we assume there's no overlap within each series, we can now replace each of those lists with lists of the form {start, height}. We can drop the "end" attribute by having a height-0 element start where the last element should have ended. (or not, if two elements were already abutting.) 
Now you can walk/recurse/pop your way through both lists in a single pass, building a new list of {start, height} outputs as you go. I see no reason you couldn't be building both your union and intersection lists at the same time.
Cleanup (conversion to a minimal representation in the original format) will be another pass, but still O(n).
So the problem is O(n*log(n)), and could be O(n) if you could finagle a way to get your input pre-sorted.
If got the following problem:
Given a series of rectangles defined by {x_min, height and x_max}, I want to efficiently compute their intersection and union, creating a new series.
For instance, if I got S1 = [{1,3,3}] and S2 = [{2,3,5}], the union would result in S3 = [{1,3,5}] and intersection in S3 = [{2,3,3}]. This would be a fairly simple case, but when S1 and S2 are a list of rectangles (unordered) It get's a little bit tricky.
My idea is trying some divide and conquer strategy, like using a modificated mergesort, and in the merge phase try to also merge those buildings. But I'm a little bit unsure about how to express this.
Basically I can't write down how to compare two rectangles with those coordinates and decide if they have to be in S3, or if I have to create a new one (for the intersection).
For the union I think the idea has to be fairly similar, but the negation (i.e. if they don't interesct).
This has to be O(nlogn) for sure, given this is in a 2D plane I surely have to sort it. Currently my first approach is O(n^2).
Any help how to reduce the complexity?
PD: The implementation I'm doing is in Python