Maximum points in a rectangle with a specific area | Need less than O(N^3)

Revision en3, by LashaBukhnikashvili, 2016-04-18 22:48:54

Here is given n(n=1000) points on the plane, each described by (x,y). need to place a rectangle of area S on the plane. Sides of a rectangle should be paralel to X and Y axis. required to find maximal number of points that can be contained by a single rectangle.

I need to find maximum O(N^2 * K) solution to solve problem, where K is answer (maximum amount of points among all rectangle with area S),

thanks in advance,

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English LashaBukhnikashvili 2016-04-18 22:48:54 2 Tiny change: 'He is given' -> 'Here is given'
en2 English LashaBukhnikashvili 2016-04-18 22:40:11 22
en1 English LashaBukhnikashvili 2016-04-18 22:30:38 480 Initial revision (published)