Tuesday, February 17, 2009

Overlapping rectangles

A set of rectangles has one border parallel to the x-axis of a Cartesian plan. Find the set of overlapping rectangles in optimal time.
Pubblicato da a
Reazioni: 

1 comment:

  1. I like this problem since it is a classical example of simple computational geometry. A solution is like the following. Sort the x-coordinates of the rectangles in time O(nlogn), and maintains the y-coordinates in a binary search tree (BST). If the current x-coordinate is on the left side of the rectangle, then insert in the BST the corresponding y-coordinates. If the current x-coordinate is on the right side of the rectangle, then remove the corresponding y-coordinates from the BST. Before inserting, search the BST to find an overlap with current y-coordinate. There are 2n search and each one takes O(logn). The total complexity is O(nlogn)

    ReplyDelete

Subscribe to: Post Comments (Atom)