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

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