The minimum covering Euclidean ball of a set of Euclidean balls in R^n

DOI10.1007/S10479-022-05138-9zbMATH Open1514.52014arXiv2001.05374OpenAlexW4313334728MaRDI QIDQ6103201FDOQ6103201

P. M. Dearing, Mark E. Cawood

Publication date: 26 June 2023

Published in: Annals of Operations Research (Search for Journal in Brave)

Abstract: Primal and dual algorithms are developed for solving the $n$-dimensional convex optimization problem of finding the Euclidean ball of minimum radius that covers $m$ given Euclidean balls, each with a given center and radius. Each algorithm is based on a directional search method in which a search path may be a ray or a two-dimensional conic section in $mathbb{R}^n$. At each iteration, a search path is constructed by the intersection of bisectors of pairs of points, where the bisectors are either hyperplanes or $n$-dimensional hyperboloids. The optimal step size along each search path is determined explicitly.

Full work available at URL: https://arxiv.org/abs/2001.05374

Recommendations

• A dual algorithm for the minimum covering ball problem in \(\mathbb R^n\)
• A primal algorithm for the weighted minimum covering ball problem in \(\mathbb {R}^n\)
• A dual algorithm for the minimum covering weighted ball problem in \({\mathbb{R}^n}\)
• A recursive algorithm for finding the minimum covering sphere of a polytope and the minimum covering concentric spheres of several polytopes
• scientific article; zbMATH DE number 1138448

zbMATH Keywords

locationconvex programmingmin-max locationminimum covering ballone-center location

Mathematics Subject Classification ID

Convex programming (90C25) Minimax problems in mathematical programming (90C47) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Discrete location and assignment (90B80)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Weighted Euclidean 1-Center Problem
• Efficient algorithms for the smallest enclosing ball problem
• Solution methodologies for the smallest enclosing circle problem
• The Minimum Covering Sphere Problem
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Algorithms - ESA 2003
• A dual algorithm for the minimum covering ball problem in \(\mathbb R^n\)
• On the spherical surface of smallest radius enclosing a bounded subset of 𝑛-dimensional euclidean space
• Title not available (Why is that?)
• A dual simplex-type algorithm for the smallest enclosing ball of balls

Cited In (2)

• Title not available (Why is that?)
• The weighted Euclidean one-center problem in \(\mathbb{R}^n\)

This page was built for publication: The minimum covering Euclidean ball of a set of Euclidean balls in \(\mathbb{R}^n\)

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