No dimension-independent core-sets for containment under homothetics

DOI10.1007/s00454-012-9462-0zbMath1258.68168OpenAlexW3102906697MaRDI 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

zbMATH Keywords

dimension reductioncomputational geometryapproximation algorithmsconvex geometry\(k\)-centergeometric inequalitiescore-setsoptimal containment

Mathematics Subject Classification ID

Convex programming (90C25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Shellability for polytopes and polyhedra (52B22)

Related Items (13)

Minkowski concentricity and complete simplices ⋮ Behaviour of inradius, circumradius, and diameter in generalized Minkowski spaces ⋮ Relating Symmetrizations of Convex Bodies: Once More the Golden Ratio ⋮ SHARPENING GEOMETRIC INEQUALITIES USING COMPUTABLE SYMMETRY MEASURES ⋮ Tightening and reversing the arithmetic-harmonic mean inequality for symmetrizations of convex sets ⋮ Diversities and the generalized circumradius ⋮ Successive radii and ball operators in generalized Minkowski spaces ⋮ On the families of successive radii and the sum of convex sets ⋮ Is a complete, reduced set necessarily of constant width? ⋮ 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 ⋮ Uniqueness of circumcenters in generalized Minkowski spaces ⋮ Clustering in Hilbert’s Projective Geometry: The Case Studies of the Probability Simplex and the Elliptope of Correlation Matrices

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

This page was built for publication: No dimension-independent core-sets for containment under homothetics