کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427565 | 686523 | 2013 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: An optimal algorithm for computing the non-trivial circuits of a union of iso-oriented rectangles An optimal algorithm for computing the non-trivial circuits of a union of iso-oriented rectangles](/preview/png/427565.png)
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.
Journal: Information Processing Letters - Volume 113, Issue 3, 15 February 2013, Pages 55–59