# A 95% minimal rectangle problem

In May, there was a question on Stackoverflow, 3 dimension prediction limit in R, a special form of the "smallest enclosing rectangle" problem. Because the problem has not been solved there, I would like to formulate it here as a problem in discrete optimization and hoping for an efficient algorithm to solve it exactly.

Given N points in, say, two dimensions, find an axes-parallel rectangle
of minimal area that encloses at least 95% of the points.

I understand there's not always a solution, for example when all the points lie on the boundary of a rectangle. So let us assume the points are somehow in general position, even such that no two points have exactly the same x- or y-coordinates.

I know that a/the solution can be found by looping through all x- and y-coordinates, resp. those below the 0.05 or above the 0.95 quantiles. Of course, I hope for a smarter and more efficient algorithmic approach.

• I don't see how your solution sketch is going to work. The problem is to find the best balance between reducing the x and y extents (from the rectangle containing all points). And this involves considering both coordinates simultaneously. Jun 5 '17 at 7:53
• @Walter Looping through the x- and y-coordinates means to enumerate and test all possible solutions. It will find the minimum with certainty. The problem is that it is not efficient, O(N^4) steps, and will not really work for more points or higher dimensions. Jun 5 '17 at 18:46
• @HansWerner Suppose you are given $N$ points in the plane. There are deterministic algorithms that compute a set of $k$ points (for any $2 \le k \le N$) with a smallest enclosing parallel axes-parallel square. This should be what you want, right? Jun 6 '17 at 8:49
• @GoHokies Thanks for pointing this out. Such a report and the literature it is referring to are quite helpful. Still, it ends up finding a square and not a rectangle, so the problem is not really solved. Seeing the effort finding a square, I am wondering whether finding a rectangle will be easier or more difficult. Jun 6 '17 at 9:22
• @HansWerner These algorithms can find rectangle-shaped enclosures as well, as demonstrated in Smallest $k$-point enclosing rectangle and square of arbitrary orientation by Das et al. Jun 6 '17 at 9:57

## 3 Answers

Your problem reads

Given $N$ points in, say, two dimensions, find an axes-parallel rectangle of minimal area that encloses at least 95% of the points.

This is essentially equivalent to the following problem (the smallest $k$-point enclosing rectangle), for which efficient deterministic algorithms are known:

Given $N$ points in two dimensions and an integer $k \le N$, find an axes-parallel square or rectangle of minimal area that encloses $k$ of the points.

Some references:

Enclosing $k$ points in the smallest axis parallel rectangle - Segal and Kedem, Information Processing Letters, 1998

Finding $k$ points with a smallest enclosing square - Smid, 1995.

Smallest $k$-point enclosing rectangle and square of arbitrary orientation - Das et al., Information Processing Letters, 2005

You can try non-deterministic algorithms, such as simulated annealing. They are not sure to get the mathematically exact answer, but they can get a good approximation fairly fast.

If $d$ is the dimension, then there are 2$d$ values to be set (locations of two opposite corners). 1. Start with corners at 2.5% and 97.5% (good approximations if the distribution is fairly well behaved). This is for 1D, otherwise $(1-0.95^{1/d})/2$ instead of 2.5%. 2. Pick two of these 2$d$ values, increase (resp. decrease) one of the two and decrease (resp. increase) the other to get back to 95%. If the area is smaller, keep it. Otherwise, apply your policy (e.g. simulated annealing: some probability to keep it that goes down with time). 3. Repeat.

• No, simulated annealing and other evolutionary approaches are in general not appropriate for solving discrete optimization problems -- I do have some experience therewith. Plus, sorry if I did not make this clear enough, I am interested in solving this problem exactly, and thus preferably in a way that could classify as combinatorial optimization. Jun 6 '17 at 8:41

Here is a sketch of an algorithm, though I have no proof that it always produces the minimum.

goal = 0.95*points.size()
rect = smallest_rectangle_containing_all(points)
while(rect.number_of_points() > goal):
old_rect = rect
rect.maximally_shrink_by_omitting_at_least_one_point()
if(rect.number_of_points() < goal)
rect = old_rect;


where rectangle::maximally_shrink_by_omitting_at_least_one_point() is a bit tricky to get right, but otherwise is straightforward (I leave its implementation to you).

• No, this is not a valid solution. Such step-by-step procedures do not work for most discrete optimization problems. For the Stackoverflow example above your approach generates a rectangle of area 21.0846. The true minimum, by the way, is 19.16451. I cannot accept your proposal as it is incorrect and does not identify the minimum area rectangle. Jun 5 '17 at 18:15