An optimal contour algorithm for iso-oriented rectangles

Reviewer: A. R. Forrest

The paper describes a time-optimum algorithm for examining the contour of the union of n iso-oriented rectangles in 2-space (iso-oriented rectangles have sides parallel to the coordinate axes). The algorithm is a development of the line sweep algorithm reported by Lipski and Preparata [1] using a modified data structure, the contracted segment tree. This permits insertion and deletion of an interval in O(log n) time, but can also report free portions of a line covered by a new interval in a time proportional to the number of free parts. It is not clear whether the new data structure would have advantages of efficiency in a practical implementation compared with rather simpler data structures. The algorithm bears a striking resemblance to the scan-line oriented hidden surface algorithms developed by Watkins [2]. It might be advantageous to reexamine Watkins' algorithm with a view to utilizing more modern data structures.