Optimal coverage of convex regions (Q1068722)

The problem of the coverage of convex regions with polygons and quadratic configurations of minimal volume is considered. The regions are presented as inequality constraints of a linear or nonlinear programming problem. It is shown that the problem of the optimal coverage with an arbitrary polygon can be reduced to a convex one of coverage with a multidimensional rectangle. If, however, rotation of the coordinate system is allowed, an additional nonconvex problem must be solved. It is also shown that, to find the minimal covering hypersphere or hyperellipsoid, one has to solve two convex programming problems. Algorithms and examples illustrating the feasibility of the proposed methods are presented.