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

DOI10.1007/S10479-022-05138-9MaRDI QIDQ6103201zbMATH OpenOpenAlexFDO

Authors P. M. Dearing, Mark E. Cawood

Publication date 26 June 2023

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

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

zbMATH Keywords

convex programminglocationmin-max locationminimum covering ballone-center location

Mathematics Subject Classification ID

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

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.

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

Cites work

• A dual algorithm for the minimum covering ball problem in \(\mathbb R^n\)
• A dual simplex-type algorithm for the smallest enclosing ball of balls
• Algorithms - ESA 2003
• Efficient algorithms for the smallest enclosing ball problem
• scientific article; zbMATH DE number 1803755 (Why is no real title available?)
• scientific article; zbMATH DE number 53540 (Why is no real title available?)
• scientific article; zbMATH DE number 194432 (Why is no real title available?)
• scientific article; zbMATH DE number 1424293 (Why is no real title available?)
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
• On the spherical surface of smallest radius enclosing a bounded subset of 𝑛-dimensional euclidean space
• Solution methodologies for the smallest enclosing circle problem
• The Minimum Covering Sphere Problem
• The Weighted Euclidean 1-Center Problem

Cited in

(8)

• A dual algorithm for the minimum covering weighted ball problem in \({\mathbb{R}^n}\)
• Is a finite intersection of balls covered by a finite union of balls in Euclidean spaces?
• A primal algorithm for the weighted minimum covering ball problem in \(\mathbb {R}^n\)
• scientific article; zbMATH DE number 5630518 (Why is no real title available?)
• The weighted Euclidean one-center problem in \(\mathbb{R}^n\)
• Finding a largest-area triangle in a terrain in near-linear time
• A sparse multicover bifiltration of linear size
• A dual algorithm for the minimum covering ball 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)