Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Maximum Number of Points on wall | Reply
Hi, I couldn't come up with a N^2 or N^2logN solution for this problem. any help is appreciated. Here is the basic problem:

basically, on a X*Y(x,y<10^9) sized wall, there are k(k<2500) integer coordinated points, a M*N(m,n < 10^9) sized rectangular panel is to be put on wall so that maximum number of points are covered. the rectangle must be put as it is, i.e you cant rotate it, its sides must be parallel to axes.

thanks in advance for any hints!
Re: Maximum Number of Points on wall (response to post by kolistivra) | Reply
It's easy too see that panel could be placed in such a way that its left and top borders contain at least one point.

So, if you fix the left border you can move the top border from down to up and count the number of points inside the panel. Use map and binary search where needed.

So, overall complexity will be depending on implementation something like O(k^2*log(k)) or O(k^2*log(k)*log(k)).
Re: Maximum Number of Points on wall (response to post by | Reply
I think you can get O(k*k*log(k)) without maps nor binary searches.
for each coordinate x:
   A = all points from [x,x+N]
   sort(A) by y coordinate
   traverse A with two pointers to find the most crowded interval

[Edit] Actually you can avoid the sort step if you have all the points sorted by y at the beginning, thus the whole algorithm becomes O(k^2)
Re: Maximum Number of Points on wall (response to post by slex) | Reply
And how are you getting A = all points from [x,x+N] if all points are sorted on y?

EDIT: Ok, I see how. So basically the problem is solved :)