No Dimension-Independent Core-Sets for Containment Under Homothetics

作者：Brandenberg Rene; Koenig Stefan

来源：Discrete & Computational Geometry, 2013, 49(1): 3-21.

DOI：10.1007/s00454-012-9462-0

• Core-sets
• Convex geometry
• Geometric inequalities
• Computational geometry
• Optimal containment
• Approximation algorithms
• Dimension reduction
• k-Center

This paper deals with the containment problem under homothetics which has the minimal enclosing ball (MEB) problem as a prominent representative. We connect the problem to results in classic convex geometry and introduce a new series of radii, which we call core-radii. For the MEB problem, these radii have already been considered from a different point of view and sharp inequalities between them are known. In this paper sharp inequalities between core-radii for general containment under homothetics are obtained.
Moreover, the presented inequalities are used to derive sharp upper bounds on the size of core-sets for containment under homothetics. In the MEB case, this yields a tight (dimension-independent) bound for the size of such core-sets. In the general case, we show that there are core-sets of size linear in the dimension and that this bound stays sharp even if the container is required to be symmetric.

• 出版日期2013-1