A recursive algorithm for finding the minimum covering sphere of a polytope and the minimum covering concentric spheres of several polytopes

DOI10.1007/BF03167575MaRDI QIDQ689920zbMATH OpenOpenAlexFDO

Authors Kazuyuki Sekitani, Yoshitsugu Yamamoto

Publication date 6 January 1994

Published in Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf03167575

zbMATH Keywords

minimum covering sphereconcentric spheressmallest sum of radiisphere with the smallest radius

Mathematics Subject Classification ID

Quadratic programming (90C20) Continuous location (90B85)

Recommendations

• A method of covering a convex polyhedral region by a minimal number of congruent spheres
• Covering a convex 3D polytope by a minimal number of congruent spheres
• Covering a simplex by spheres: complexity and algorithms
• An algorithm for constructing the convex hull of a set of spheres in dimension \(d\)
• Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere
• The minimum covering \(l_{pb}\)-hypersphere problem
• New analysis of the sphere covering problems and optimal polytope approximation of convex bodies
• A dual algorithm for the minimum covering ball problem in \(\mathbb R^n\)
• An algorithm for concave integer minimization over a polyhedron

Cites work

• scientific article; zbMATH DE number 3127495 (Why is no real title available?)
• scientific article; zbMATH DE number 3562783 (Why is no real title available?)
• A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes
• A simple algorithm for computing the smallest enclosing circle
• Finding the nearest point in A polytope
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
• Single Facility $l_p $-Distance Minimax Location
• The Minimum Covering Sphere Problem
• The Weighted Euclidean 1-Center Problem
• The weighted Euclidean 1-center problem
• Weighted min-max location problems: Polynomially bounded algorithms

Cited in

(12)

• CONSTRAINED OPTIMAL LOCATION
• Calculating a minimal sphere containing a polytope defined by a system of linear inequalities
• Chebyshev centres, Jung constants, and their applications
• Minimal ellipsoid circumscribing a polytope defined by a system of linear inequalities
• A primal algorithm for the weighted minimum covering ball problem in \(\mathbb {R}^n\)
• A dual algorithm for the minimum covering ball problem in \(\mathbb R^n\)
• Covering a convex 3D polytope by a minimal number of congruent spheres
• The minimum covering Euclidean ball of a set of Euclidean balls in \(\mathbb{R}^n\)
• scientific article; zbMATH DE number 3913428 (Why is no real title available?)
• An efficient search algorithm for minimum covering polygons on the sphere
• A dual algorithm for the minimum covering weighted ball problem in \({\mathbb{R}^n}\)
• Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere

This page was built for publication: A recursive algorithm for finding the minimum covering sphere of a polytope and the minimum covering concentric spheres of several polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q689920)