The contour problem for rectilinear polygons (Q802313)

This paper presents yet another algorithm to solve the contour problem for the union of a set of rectangles or orthogonal polygons. The algorithm is both time- and space-optimal, requiring O(n log n\(+e)\) time and O(n) space, if the input has a total of n vertices and the output has a total of e vertices. The only other algorithm with this performance is the one due to Güting. However his algorithm relies on a complex data structure while the algorithm given here uses a simple variation on the segment tree. Indeed when the input consists solely of rectangles the solution is almost as simple as the original and non-optimal Lipski and Preparata algorithm.