2
$\begingroup$

I am having some confusion about finding the area of union of $n$ axis parallel rectangles in $O(n\log n)$ by the line sweep method. The following pictures are from the book of Shamos and Preparata. enter image description here

In this case one needs to find the total height of the shaded region efficiently. So initially build a segment tree with the y-coordinates.This can be done in $O(n\log n)$. (Sorting $O(n\log n)$ and building the tree $O(n)$). The following pseudo code calculates the area.enter image description here Here $b_i$ and $e_i$ are respectively the minimum and maximum ordinate at $X[i]$. $m[v]$ is the contribution of interval associated with node $v$. The code for INSERT is

PROCEDURE INSERT(b,e;v):
    if(b <= B[v] and $e >= E[v]) then
        C[v] = C[v]+1
    else
     if(b < floor((B[v]+E[v])/2)) then
         insert(b,e;LSON(v))
     if(e > floor((B[v]+E[v])/2)) then
         insert(b,e;RSON(v))
     UPDATE(v)

DELETE has similar structure And procedure for UPDATE (at line 9) is

PROCEDURE UPDATE(v) :
    if (C[v] != 0) then 
        M[v] = E[v]-B[v]
     else if(v is not a leaf node) then
        M[v] = M[LSON(v)] + M[RSON(v)]
     else
        M[v] = 0

I do not understand how $m[root(T)]$ is the total height of the shaded region. It would also include the height of the 'not shaded' region and therefore computes the total area swept by the sweep line during two consecutive event points, not the actual area of the intersected rectangle. Can someone please help me understand this. Thank you. Also if some one can provide the link of the original papers (by Victor klee and Bentley), it will be much appreciated. I have looked through internet in vain.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.