I'm not sure this problem is so well specified. For example, what happens when parts of edges "poke out" from the contour? You've said you can't remove edges so the only way the contour is well defined is if the contour has no "burrs".
Regardless, the algorithm you probably want to look at is called the Vatti clipping algrithm. Vatti's algorithm does arbitrary boolean operations (union, intersection, difference, xor) on two dimensional polygons. My apologies, I'm having trouble finding the run time through a cursory glance but I believe it's linear (or maybe $O( V\ ln(V))$) in the number of total polygon vertices, $V$. It uses a sweep line approach so besides whatever structures are used to store, sort, search, etc., the fundamental operation is scanning through the vertices which probably isn't much worse than linear.
By interpreting your problem as trying to find a (potentially convex) contour of many thin rectangles in the plane, you can use Vatti's clipping algorithm to get the contour. Here is one such way:
- Do a large union of all the rectangles in the plane
- Discard all 'holes' and consider only the outer contours
- Do another union on all the outer contours
The reason for the multiple applications of Vatti's algorithm is that you can have polygon 'islands' that are completely enclosed (and not part of) an outer polygon contour. Discarding the holes will ensure the middle will get 'filled in' and the resulting polygon will be the union of all the contours. If there's a simple way to determine what the 'outer contour' is, then that would obviously be better but I don't know of any way to accomplish that without re-inventing Vatti's algorithm.
One can also imagine using some type of polygon offsetting to either fill out breaks in the contour or make the contour smoother.