An optimal algorithm for computing the non-trivial circuits of a union of iso-oriented rectangles
Given n rectangles R-1, ..., R-n on the plane with sides parallel to the coordinate axes, Lipski and Preparata (1981) [1] have presented a Theta(n log n) time and O(n log n) space algorithm for computing the non-trivial circuits of the union u = R-1 boolean OR ... boolean OR R-n. In this paper, we are presenting a simple algorithm, which computes the non-trivial circuits of u in Theta(n log n) time and Theta(n) space. (C) 2012 Elsevier B.V. All rights reserved.
optimal algorithm circuit computational geometry contour rectilinear polygons sweep plane