Abstract
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 (Eur. J. Oper. Res. 29:98–110, 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 (Eur. J. Oper. Res. 29:98–110, 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agarwal, P., Har-Peled, S., Varadarajan, K.R.: Geometric approximation via coresets. In: Goodman J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry. MSRI Publications, vol. 52. Cambridge University Press, Cambridge (2005)
Bonnesen, T., Fenchel, W.: Theorie der konvexen Körper. Springer, Berlin (1974). Translation: Theory of Convex Bodies. BCS Associates, Moscow, Idaho (USA) (1987)
Brandenberg, R., Roth, L.: New algorithms for k-center and extensions. J. Comb. Optim. (2009, to appear)
Brandenberg, R., Gerken, T., Gritzmann, P., Roth, L.: Modeling and optimization of correction measures for human extremities. In: Jäger, W., Krebs, H.-J. (eds.) Mathematics—Key Technology for the Future. Joint Projects between Universities and Industry 2004–2007, pp. 131–148. Springer, Berlin (2008)
Bădoiu, M., Clarkson, K.L.: Smaller coresets for balls. In: Proc. 14th ACM-SIAM Sympos. Discrete Algorithms, pp. 801–802 (2003)
Bădoiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Annual ACM Symposium on Theory of Computing archive. Proc. 34th Annu. ACM Sympos. Theory of Computing, pp. 250–257. ACM, New York (2002)
Eaves, B.C., Freund, R.M.: Optimal scaling of balls and polyhedra. Math. Program. 23, 138–147 (1982)
Fischer, K., Gärtner, B., Kutz, M.: Fast smallest-enclosing-ball computation in high dimensions. In: Proc. 11th Annual European Symposium on Algorithms (ESA), pp. 630–641 (2003)
Gärtner, B.: Fast and robust smallest enclosing balls. In: Proc. 7th Annu. European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 1643, pp. 325–338. Springer, Berlin (1999)
Grant, M., Boyd, S., Ye, Y.: Disciplined convex programming. In: Liberti, L., Maculan, N. (eds.) Global Optimization: From Theory to Implementation, Nonconvex Optimization and Its Applications. Kluwer, Dordrecht (2005)
Grant, M., Boyd, S., Ye, Y.: cvx Users’ guide, version 1.0. http://www.stanford.edu/~boyd/cvx/cvx_usrguide.pdf, June 2006
Gritzmann, P., Klee, V.: Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces. Math. Program. 59, 163–213 (1993)
Gritzmann, P., Klee, V.: On the complexity of some basic problems in computational convexity I: Containment problems. Discrete Math. 136, 129–174 (1994)
Grötschel, M., Lovasz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2. Springer, Berlin (1993)
Halperin, D., Sharir, M., Goldberg, K.: The 2-center problem with obstacles. J. Algorithms 42, 109–134 (2002)
Klee, V.: Circumspheres and inner products. Math. Scand. 8, 363–370 (1960)
Kumar, P., Mitchell, J.S.B., Yıldırım, E.A.: Approximate minimum enclosing balls in high dimensions using core-sets. J. Exp. Algorithmics 8, 1.1 (2003)
Nielsen, F., Nock, R.: Approximating smallest enclosing balls. In: Nielsen, F., Nock, R. (eds.) Proceedings of International Conference on Computational Science and Its Applications (ICCSA). Lecture Notes in Computer Science, vol. 3045. Springer, Berlin (2004)
Plastria, F.: Solving general continous single facility location problems by cutting planes. Eur. J. Oper. Res. 29, 98–110 (1987)
Pólik, I.: Addendum to the SeDuMi user guide version 1.1. Technical report, Advanced Optimization Laboratory, McMaster University (2005)
Roth, L.: Exakte und ε-approximative Algorithmen zur Umkugelberechnung. Diploma thesis, Zentrum Mathematik, TU München, October 2005
Schneider, R.: Convex Bodies: The Brunn-Minkowski Theory. Encyclopedia of Mathematics and Its Applications, vol. 44. Cambridge University Press, Cambridge (1993)
Sturm, J.F.: Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optim. Methods Softw. 11-12, 625–653 (1999)
Welzl, E.: Smallest enclosing disks (balls and ellipsoids). In: Maurer, H. (ed.) New Results and New Trends in Computer Science. Lecture Notes in Computer Science, vol. 555, pp. 359–370. Springer, Berlin (1991)
Yao, A.C.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. 11, 721–736 (1982)
Zhou, G.L., Toh, K.C., Sun, J.: Efficient algorithms for the smallest enclosing ball problem. Comput. Optim. Appl. 30(2), 147–160 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
L. Roth has been supported by the “Deutsche Forschungsgemeinschaft” through the graduate program “Angewandte Algorithmische Mathematik”, Technische Universität München.
Rights and permissions
About this article
Cite this article
Brandenberg, R., Roth, L. Minimal containment under homothetics: a simple cutting plane approach. Comput Optim Appl 48, 325–340 (2011). https://doi.org/10.1007/s10589-009-9248-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-009-9248-3