to find if any overlapping rectangles exist in n number of rectangles

Question

Assume that each rectangle is rectilinearly oriented (sides parallel to the x- and y-axes), so that we represent a rectangle by its minimum and maximum xand y-coordinates. Give an O.n lg n/-time algorithm to decide whether or not a set of n rectangles so represented contains two rectangles that overlap. Your algorithm need not report all intersecting pairs, but it must report that an overlap exists if one rectangle entirely covers another, even if the boundary lines do not intersect.

my solution: Let R be an array containing rectangles represented as (x_int, y_int) where x_int represents interval [x1, x2] and y_int represents interval [y1, y2] if the 4 cornesrs of rectacle are (x1, y1), (x1, y2), (x2, y1) and (x2, y2).Let the indexing start from 1. this solution is based on the fact that two rectangles overlap if and only if their x_int overlap and y_int overlap.

FindOverlap(R, n):
  T = IntervalTree()   // T is a interval tree capable of checking if a given
                       // interval is overlapping with any interval in the tree
                       // and inserting interval in the tree in log(n) time.
  for i in [1,n]:
      x_int, y_int = R[i][1], R[i][2]

      interval_Index = T.IntervalSearch(x_int)  // Returns 0 if there is no interval 
                                           // in T which overlaps x_int , else 
                                           // returns index of the interval which
                                           // overlaps x_int 
      if interval_Index != 0:

          if R[interval_Index][2] overlaps y_int:

              return i, interval_Index

      T.InsertInterval(x_int, i)          // inserts interval x_int into T with 
                                          //associated index i
  return False        

Is there anything wrong in this ? Will this algorithm work correctly?

Answer 1

Here's a scan line algorithm that meets the requirements:

You'll need a binary search tree (BST) that keeps rectangles ordered by min X coordinate, and a priority queue that keeps rectangles ordered by max Y coordinate.

1. Sort the rectangles by min Y coordinate: O(N log N)
2. Iterate through the rectangles in min Y order. For each one:
   1. Remove all rectangles with max Y coordinates less than the new rect min Y from both the priority queue and the BST: O(N log N) all together
   2. Insert the new rectangle into the BST. If you detect that its X interval overlaps with the rectangles to its left or right in the BST, then you've found an overlap and you're done. This step also takes O(N log N) all together.
   3. Insert the new rectangle into the priority so that you know when to remove it in step 2.1. Again O(N log N)