### Usu's blog

By Usu, history, 5 years ago,

Hey! Does anybody have a solution in n log n for this? Given n rectangles, determinate a point which is included by a maximum number of rectangles (including the boundaries).

• +34

 » 5 years ago, # |   +24 It can be solved with sweep line algo and segment tree in $O(N \lg N)$. For each rectangle $[x_1, x_2] \times [y_1, y_2]$, produce two events $(x_1, (y_1, y_2), +)$ and $(x_2, (y_1, y_2), -)$. Sort all the events (there are $2N$ such many) by $x$. From minimum $x$ to maximum $x$, if it's from left side of some rectangle ($(x_1, (y_1, y_2), +)$), add 1 to all the points in the closed interval $[y_1, y_2]$, otherwise, subtract 1 to those in the closed interval $[y_1, y_2]$. After each addition or subtraction, find the maximum value among all possible $y$ which is a candidate to the answer(update the answer). Addition/Subtraction on an interval and querying maximum value can be done with segment tree in $O(\lg C)$ per operation, where $C$ is the range of values. If we first normalize all the value $y$, it can be reduced to $O(\lg N)$.
•  » » 5 years ago, # ^ |   +24 I think that when sweeplining, for a certain x, you should perform all addition events for that x, then check for a new max, then all subtraction events for that x. Otherwise you might miss the correct answer if you perform a subtraction, then a query, then an addition.
•  » » » 5 years ago, # ^ |   +20 Yes, I just give a rough idea. Those parts should be taken care when implementing.
•  » » » » 5 years ago, # ^ |   +10 It’s a very nice sketch. I just wanted to add the detail since I had also been thinking of the same solution for a little bit. I hope it helps the asker.
•  » » » » » 5 years ago, # ^ |   +8 Yes, it helped me. Is this algorithm similar to that one: "find the number of intersections of segments, all segments parallel either Ox either Oy"? I think they are 90% the same, am I wrong?
•  » » » » » » 5 years ago, # ^ |   0 You can think of each segment of length L as an 1xL or an Lx1 rectangle, so the rectangle problem is a generalization of the line segment problem.