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.