No dimension-independent core-sets for containment under homothetics
From MaRDI portal
Publication:1942308
DOI10.1007/s00454-012-9462-0zbMath1258.68168MaRDI QIDQ1942308
René Brandenberg, Stefan König
Publication date: 18 March 2013
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-012-9462-0
dimension reduction; computational geometry; approximation algorithms; convex geometry; \(k\)-center; geometric inequalities; core-sets; optimal containment
90C25: Convex programming
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
52B22: Shellability for polytopes and polyhedra
Related Items
Clustering in Hilbert’s Projective Geometry: The Case Studies of the Probability Simplex and the Elliptope of Correlation Matrices, Relating Symmetrizations of Convex Bodies: Once More the Golden Ratio, Tightening and reversing the arithmetic-harmonic mean inequality for symmetrizations of convex sets, Diversities and the generalized circumradius, On the families of successive radii and the sum of convex sets, The asymmetry of complete and constant width bodies in general normed spaces and the Jung constant, Additive colourful Carathéodory type results with an application to radii, Successive radii and ball operators in generalized Minkowski spaces, Is a complete, reduced set necessarily of constant width?, Uniqueness of circumcenters in generalized Minkowski spaces, Behaviour of inradius, circumradius, and diameter in generalized Minkowski spaces, Minkowski concentricity and complete simplices, SHARPENING GEOMETRIC INEQUALITIES USING COMPUTABLE SYMMETRY MEASURES
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimal containment under homothetics: a simple cutting plane approach
- New algorithms for \(k\)-center and extensions
- Practical methods for shape fitting and kinetic data structures using coresets
- Kolmogorov diameters of a regular simplex
- Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
- A generalization of Jung's theorem
- Helly-type theorems and generalized linear programming
- On the complexity of some basic problems in computational convexity. I. Containment problems
- A subexponential bound for linear programming
- Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
- Optimal core-sets for balls
- Excursions into combinatorial geometry
- Convex regions and projections in Minkowski spaces
- Approximate clustering via core-sets
- A combinatorial bound for linear programming and related problems
