An optimal algorithm for computing the non-trivial circuits of a union of iso-oriented rectangles

Given n   rectangles R1,…,RnR1,…,Rn on the plane with sides parallel to the coordinate axes, Lipski and Preparata (1981) [1] have presented a Θ(nlogn) time and O(nlogn) space algorithm for computing the non-trivial circuits of the union U=R1∪⋯∪RnU=R1∪⋯∪Rn. In this paper, we are presenting a simple algorithm, which computes the non-trivial circuits of UU in Θ(nlogn) time and Θ(n)Θ(n) space.

► We compute the non-trivial circuits of a union of n   iso-oriented rectangles. ► We present a simple Θ(nlogn)-time and Θ(n)Θ(n)-space algorithm. ► Our algorithm is based on the following simple idea. ► Each arc of a non-trivial circuit C is visible from an endpoint of a non-trivial arc of C. ► Our algorithm uses the well-known technique of plane sweeping.