Saturday, September 26, 2026

minimum enclosing rectangle for k out of n points

The problem of finding the smallest enclosing axis-aligned rectangle around a given set of points is trivial. We don't need an optimization model for that.

Things are more interesting if we need to cover just k out of n points. The model needs to select the k points and then form a rectangle around them such that the size of the rectangle (the area) is minimized. 


In this example we have n=100 and k=25. 

There are algorithms for this (see e.g. [1,2]). Here, of course, we try to solve this using an optimization model that finds proven, globally optimal solutions.