EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3898. The minimum covering Euclidean ball problem: review and report

Invited abstract in session TB-61: Nonlinear Location Optimization, stream Locational Analysis.

Tuesday, 10:30-12:00
Room: S10 (building: 101)

Authors (first author is the speaker)

1. Mark Cawood
Mathematical and Statistical Sciences, Clemson University
2. Lin Dearing
Mathematical and Statistical Sciences, Clemson University

Abstract

Efficient primal and dual algorithms have been developed recently by the authors for the n-dimensional minimum covering Euclidean ball problem of several types. These include the minimum covering ball of a given finite set of distinct points, the minimum covering ball of a given finite set of balls each with different radius and center, and the minimum covering ball of a set of distinct points with weighted Euclidean distance between the points and the center of the covering ball. Each problem type corresponds to an equivalent one-center location problem.

The common approach for each algorithm is a search-path method, where the search path is determined by the intersection of bisectors of pairs of points. Each problem has a different structure for the bisectors of pairs of points (hyperplanes, hyperboloids, and hyperspheres, respectively). The step size along the search path is computed exactly at each iteration. Each point on the search path is primal (dual) feasible and satisfies complementary slackness for the primal (dual) algorithm.

Example problems are presented for each problem type and illustrate the bisectors, their intersection, and the optimality conditions. Computational results are presented.

Current work is presented on the combined problem of finding the minimum covering Euclidean ball of a given set of balls with weighted distance. The bisector of a pair of points is a quartic surface.

Keywords

Status: accepted

Back to the list of papers