Best fixed rectangular area fit over points

I'm using Google Maps and I'm trying to work out the maximum number of points visible in the viewport at a given zoom level.

My naive approach is to get the viewing area (in coordinates) and use that as a "fitting rectangle" and see how many points fit in the area. I had a look around but I couldn't find any algorithm for "best fit" of random points in a rectangular area.

It seems a quite common problem so I probably don't know the right keywords to use.

Any help in getting me to a solution would be appreciated.

EDIT: thanks for the answers but I'm afraid I didn't make myself clear. Fitting a rectangle over ALL the points is pretty much a trivial affair (sort them all, get the min/max and voilà).

What I want to know is the maximum number of points that can be fit under a FIXED SIZED rectangle: I've got all my points and a "moving w开发者_JAVA百科indow" of fixed size and I want to know how many points I can fit in.

Sorry for the bad initial explanation.

Cheers.

---

To find a best-fit rectangle over a set of points, and with the assumption that all points in the set need to be within the rectangle, all you need to do is find the min/max in both dimensions.

One way to do this would be to sort the points by their X dimension and take the first and last as the min/max in that dimension, and then repeat the process in the Y dimension to get that min/max. From that information, you have all you need to make a rectangle.

From a computational complexity standpoint, the complexity is 2x the complexity of the sort algorithm used (since you have to sort 2 times) + the complexity of getting the first and last elements of each sorted set, which, if you use an array, for example, is an O(1) operation.

If you use merge sort, and sort into arrays, you have an overall complexity of O(n log n). Broken down into number of operations, you have 2(n log n) + 4.

This wont give you the tightest fit on the set of rectangles because it won't ensure that one side of the rectangle is collinear with at least 2 of the points (for that you will need the Rotating Calipers algorithm that @Bart Kiers suggestes), but it is a much faster algorithm since the rotating calipers does esentially the same as I have described here, but then rotates the rectangle until one of it's edges lines up with 2 of the min/max points.