Minimal containment under homothetics: a simple cutting plane approach

Minimal containment problems arise in a variety of applications, such as shape fitting and packing problems, data clustering, pattern recognition, or medical surgery. Typical examples are the smallest enclosing ball, cylinder, slab, box, or ellipsoid of a given set of points. Here we focus on one of the most basic problems: minimal containment under homothetics, i.e., covering a point set by a minimally scaled translation of a given container. Besides direct applications this problem is often the base in solving much harder containment problems and therefore fast solution methods are needed, especially in moderate dimensions. While in theory the ellipsoid method suffices to show polynomiality in many cases, extensive studies of implementations exist only for Euclidean containers. Indeed, many applications require more complicated containers. In Plastria (1987) the problem is discussed in a more general setting from the facility location viewpoint and a cutting plane method is suggested. In contrast to Plastria (1987), our approach relies on more and more accurate approximations of the container. For facet and vertex presented polytopal containers the problem can be formulated as an LP, and for many general containers as an SOCP. The experimental section of the paper compares those formulations to the cutting plane method, showing that it outperforms the LP formulations for vertex presented containers and the SOCP formulation for some problem instances.