Cited By
View all- Bryant DHuber KMoulton VTupper P(2023)Diversities and the Generalized CircumradiusDiscrete & Computational Geometry10.1007/s00454-023-00493-170:4(1862-1883)Online publication date: 1-Dec-2023
No Dimension-Independent Core-Sets for Containment Under Homothetics
Pages 3 - 21
Abstract
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.
References
[1]
Amenta, N.: Helly-type theorems and generalized linear programming. Ph.D. thesis, University of California at Berkeley (1992)
[2]
Badoiu, M., Clarkson, K.L.: Smaller core-sets for balls. In: SODA'03: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 801---802. SIAM, Philadelphia (2003)
[3]
Badoiu, M., Clarkson, K.L.: Optimal core-sets for balls. Comput. Geom. 40(1), 14---22 (2008)
[4]
Badoiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: STOC'02: Proc. of the 34th Annual ACM Symposium on Theory of Computing, pp. 250---257. ACM, New York (2002)
[5]
Bohnenblust, H.F.: Convex regions and projections in Minkowski spaces. Ann. Math. 39, 301---308 (1938)
[6]
Boltyanski, V., Martini, H., Soltan, P.S.: Excursions Into Combinatorial Geometry. Universitext (1997)
[7]
Bonnessen, T., Fenchel, W.: Theorie der Konvexen Körper. Springer, Berlin (1934). Translation: Theory of Convex Bodies. BCS Associates, Moscow, Idaho, USA, 1987
[8]
Brandenberg, R., Roth, L.: New algorithms for k-center and extensions. J. Comb. Optim. 18, 376---392 (2009)
[9]
Brandenberg, R., Roth, L.: Minimal containment under homothetics: a simple cutting plane approach. Comput. Optim. Appl. 48, 325---340 (2011)
[10]
Brandenberg, R., Swanepoel, K.: Private communication (2006)
[11]
Clarkson, K.L.: Coresets, sparse greedy approximation, and the Frank---Wolfe algorithm. In: SODA'08: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 922---931. SIAM, Philadelphia (2008)
[12]
Danzer, L., Grünbaum, B., Klee, V.: Helly's theorem and its relatives. In: Klee, V. (ed.) Convexity, Proc. Symp. Pure Math., vol. 13, pp. 101---180. American Mathematical Society, Providence (1963)
[13]
Goel, A., Indyk, P., Varadarajan, K.: Reductions among high dimensional proximity problems. In: SODA'01: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 769---778. SIAM, Philadelphia (2001)
[14]
Gritzmann, P., Klee, V.: Inner and outer j-radii of convex bodies in finite-dimensional normed spaces. Discrete Comput. Geom. 7, 255---280 (1992)
[15]
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)
[16]
Gritzmann, P., Klee, V.: On the complexity of some basic problems in computational convexity. I. Containment problems. Discrete Math. 136, 129---174 (1994)
[17]
Grünbaum, B.: Measures of symmetry for convex sets. Proc. Symp. Pure Math. 1(Convexity), 271---284 (1963)
[18]
Henk, M.: A generalization of Jung's theorem. Geom. Dedic. 42, 235---240 (1992)
[19]
Jung, H.W.E.: Über die kleinste Kugel, die eine räumliche Figur einschließt. J. Reine Angew. Math. 123, 241---257 (1901)
[20]
Matousek, J., Sharir, M., Welzl, E.: A subexponential bound for linear programming. Algorithmica 16(4---5), 498---516 (1996)
[21]
Panigrahy, R.: Minimum enclosing polytope in high dimensions. CoRR, arXiv:cs.CG/0407020 (2004)
[22]
Pukhov, S.V.: Kolmogorov diameters of a regular simplex. Mosc. Univ. Math. Bull. 35, 38---41 (1980)
[23]
Rockafellar, R.T.: Convex Analysis. Princeton Landmarks in Mathematics and Physics. Princeton University Press, Princeton (1996)
[24]
Saha, A., Vishwanathan, S.V.N., Zhang, X.: New approximation algorithms for minimum enclosing convex shapes. In: SODA'11. SIAM, Philadelphia (2011)
[25]
Schneider, R.: Convex Bodies: The Brunn---Minkowski Theory. Cambridge University Press, Cambridge (1993)
[26]
Sharir, M., Welzl, E.: A combinatorial bound for linear programming and related problems. In: STACS'92: Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, pp. 569---579. Springer, London (1992)
[27]
Yu, H., Agarwal, P.K., Varadarajan, K.R., Poreddy, R.: Practical methods for shape fitting and kinetic data structures using coresets. Algorithmica 52(3), 378---402 (2007)
- No Dimension-Independent Core-Sets for Containment Under Homothetics
Recommendations
No dimension independent core-sets for containment under homothetics
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometryThis paper deals with the containment problem under homothetics, a generalization of the minimal enclosing ball (MEB) problem. We present some new geometric identities and inequalities in the line of Jung's Theorem and show how those effect the hope on ...
New Algorithms for k-Center and Extensions
COCOA 2008: Proceedings of the 2nd international conference on Combinatorial Optimization and ApplicationsThe problem of interest is covering a given point set with homothetic copies of several convex containers C 1, ..., C k , while the objective is to minimize the maximum over the dilatation factors. Such k -containment problems arise in various ...
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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2013 Springer Science+Business Media New York.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 January 2013
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Nov 2024
Other Metrics
Citations
Cited By
View all- Bryant DHuber KMoulton VTupper P(2023)Diversities and the Generalized CircumradiusDiscrete & Computational Geometry10.1007/s00454-023-00493-170:4(1862-1883)Online publication date: 1-Dec-2023
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in