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.