Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
I have set of spatial points defined by coordinates (x,y) . I want to find the bounding rectangle of given area that maximizes the number of point inside the rectangle. The obtained rectangle should have sides parallel to coordinate axes.
Please suggest.
Maybe (repeat, maybe) first find the bounding rectangle, regardless of area, as described by "Mandrill" above (who apparently overlooked your "given area" constraint). Then your "given area rectangle" will be inside that. Or, if that bounding rectangle is already your given area or less, then you're done. If not, choose any corner, and start moving it "inwards" in x, losing one point for sure, until you hit a second point. Then move it "inwards" in y until you again hit a second point. So that shrinks the rectangle as much as possible, while losing only the outermost point with respect to the selected corner. Save the resulting area. Now re-start with the original rectangle, and try each of the three other corners in turn. So you'll have four rectangles, each with one point lost. Choose the minimum-area rectangle from among these four. And now start again with that rectangle. Etc,etc, until you get the requisite area.
Now, this will certainly get you a "local minimum". But I'm not at all sure it'll get you the "global minimum".
Here is a simple brute-force approach. Let A be the given area and n the number of points.
Find the bounding box of all points. If its area is smaller or equal than A, you are finished (a rectangle of size < A can be always trivially extended to a rectangle of size A).
Generate all "(n-1)-subsets" (subsets of size n-1) of the set of all points. Test their bounding boxes as in 1. Stop if you found one.
Generate all "(n-2)-subsets", test their bounding boxes, then all n-3-subsets, and so on. See this old SO post how to generate k-subsets in general.
Beware, worst case running time of this algorithm might be O(2^n). If that approach is ok, or too slow for your case depends on n, A, and the actual distribution of the points.
