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

DOI10.1007/BF03167575zbMATH Open0797.90056OpenAlexW2003555453MaRDI QIDQ689920FDOQ689920

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

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

zbMATH Keywords

minimum covering sphereconcentric spheressmallest sum of radiisphere with the smallest radius

Mathematics Subject Classification ID

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

Cites Work

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

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\)
• Title not available (Why is that?)
• 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)