4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ – Walter Jun 5 '17 at 7:53
  • $\begingroup$ @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. $\endgroup$ – Hans W. Jun 5 '17 at 18:46
  • 1
    $\begingroup$ @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? $\endgroup$ – GoHokies Jun 6 '17 at 8:49
  • $\begingroup$ @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. $\endgroup$ – Hans W. Jun 6 '17 at 9:22
  • $\begingroup$ @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. $\endgroup$ – GoHokies Jun 6 '17 at 9:57
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Hans W. Jun 6 '17 at 8:41
-1
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Hans W. Jun 5 '17 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.