Given a collection of points, I'd like to find the center of a bounding box (fixed-length and width) that maximizes the number of points within said box. I'm at a loss for an efficient way to do this.
Algorithm with complexity O(N^2*logN) (I hope that better one exists):
Edit: article exploiting interval trees claims O(NlogN) complexity
Sort data array A by X coordinate.
Scan A with sweep line left to right.
For every point in A get LeftX = A[k].X - left coordinate of vertical band, find the rightmost coordinate of vertical band RightX = LeftX + Width.
Copy points inside the band to another array B.
Sort B by Y-coordinate.
Scan B width sweep line top to down.
For every point B[i] get TopY = B[i].Y - top coordinate of rectangle, calculate BottomY = TopY + Height.
Use binary search in B:
B[j] is the last bottom point in B with B[j].Y <= BottomY.
Find number of points in the current rectangle:
Number of points is N(k, i) = j - i + 1
Check whether N(k, i) is maximum among others