O(N^2) naiive algorithm is obvious - check every pair of rectangles. This problem can be done in O(N log N) using a data structure called an R tree or a QuadTree.
If you want to use and R Tree - read: http://en.wikipedia.org/wiki/R-tree The QuadTree approach is very simple. Maintain something similar to a 4-ary tree. The key value for the 4-ary tree is a corner point of the rectangle. Each of the 4 children of the node corresponds to a particular quadrant in 2D space. Split the 2D space into 4 quadrants using that particular point. Eg. . . . . | . . . . . . . . | . . . . - - - - x - - - - . . . . | . . . . . . . . | . . . . *The idea: * Since we are dealing with non-overlapping rectangles, no rectangle inserted into this data structure should include the point x. *Data Structure:* A 4-ary tree with coloured edges. A black coloured edge means that there is no relationship between the parent and child point. A red coloured edge means that the parent and child together make a rectangle. *Invariant:* Every inserted rectangle is represented by a parent-child node pair with a red edge between them. *Insert procedure:* For each rectangle (x1, y1), (x2,y2): 1. Insert (x1, y1) into the Quadtree - mark the inserted edge as black. Make sure (using the red edges) that you're not inserting the point within a rectangle that's already been inserted. 2. Insert (x2, y2) into the Quadtree in a fashion similar to (1) - make sure that the immediate parent of (x2, y2) at the time of insertion is (x1, y1). If not, output the rectangle corresponding to the parent and this rectangle as the overlapping pair. 3. Mark the inserted edge as red. If all rectangles were inserted correctly, no overlapping rectangles will be found. Else, you will be able to find an overlapping rectangle in step 1 or 2. Time complexity: O(N log N) Space complexity: O(N) @SAMMM: A line sweep algorithm is O(N^2) Counter Case: Stacked Rectangles xxxxxxxxxxxxx yyyyyyyyyyyyy zzzzzzzzzzzzz aaaaaaaaaaaaa If you're sweeping via X coordinate, N C 2 comparisons are done for each starting vertex. -- DK http://twitter.com/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Gm5RD4v39HYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
