Minisum hyperspheres (Q2430558)

Consider the \(n\)-dimensional Euclidean space \({\mathbb R}^n\) with a given norm \(\|\cdot\|\) and associated distance \(d\). Given \(X\in {\mathbb R}^n\) and \(r>0\), the hypersphere \(S(X,r)\) is defined as the set \(\{Y\in {\mathbb R}^n : \|X-Y\|=r\}\). The space of hyperspheres will be denoted by \({\mathcal G}\). Given a set of points \({\mathcal D}=\{A_1,\ldots,A_M\}\subset {\mathbb R}^n\), and positive weights \(\omega_i\), \(i=1,\ldots,M\), one may consider the problem of minimizing the functional \[ S\in {\mathcal G}\mapsto \sum_{m=1}^M\omega_m\,d(S,A_m), \] where \(d(S,A_m)\) is the distance from the point \(A_m\) to the hypersphere \(S\). A minimum of this functional is called a \textit{minisum hypersphere}. This problem may be considered as a generalization of the Weber problem, a more general version of the Fermat-Torricelli problem (given three fixed-points in the plane, find a fourth one such that the sum of the distances between the new point and the fixed-points is minimal). As the author writes in the Preface: ``The minimax hypersphere problem can be stated in very simple terms but there is no elementary way to solve the problem in general.'' In this monograph, research of the author concerning this problem is presented. The book is divided into six chapters. In the first one, a concise introduction to minisum hyperspheres is given. Related questions (such as the minimax hypersphere problem, the center problem, or the least squares hypersphere problem) and applications (such as the equity facility location problem) are presented. Some mathematical preliminaries are presented: different types of norms, bisectors, and finite dominating sets are discussed. In Chapter~2 the minisum hypersphere problem for the Euclidean norm in \({\mathbb R}^n\) is treated. Existence of optimal solutions following the paper by \textit{Y. Nievergelt} [Numer. Math. 114, No. 4, 573--606 (2010; Zbl 1202.65018)] is proven in the class \(\overline{\mathcal G}\) of generalized hyperspheres (hyperspheres and hyperplanes). A criterion on the set \({\mathcal D}\) excluding hyperplanes as solutions is given on Theorem~2.9. Examples of sets of points for which every optimal solution is a hyperplane are given in Lemma~2.8. Incidence properties of solutions are discussed in Section~2.5. Arbitrary norms in \({\mathbb R}^n\) are considered in Chapter~3. The main result, Theorem~3.10, is that a polyhedral norm always contains a minisum hypersphere. Examples of degenerate solutions can be found in Section~3.3. In Section~3.6, a geometric description of the set of centers of minisum circles for polyhedral norms in \({\mathbb R}^2\) is given. In Chapter~4, a different approach is taken. In the Euclidean plane \({\mathbb R}^2\), a norm \(\|\cdot\|\) is used to compute the hyperspheres, but a different norm \(k\) measures the distance between the hypersphere and the given points. For the case of two unequal polyhedral norms existence of minisum circles in proven in Theorem~4.19, and a finite dominating set is derived in Theorem~4.20. In Chapter~5, the theory developed in the previous chapter is used to analyze different variants of the problem of locating a nondegenerated, axis-parallel rectangle. In Chapter~6, two extensions of the minisum hypersphere problem are considered. In the first one, positive and negative weights are considered. In the second one, the points \(A_1,\ldots,A_M\) are replaced by closed bounded sets. The text is comprehensive and precise references are given. Every chapter concludes with an interesting concluding remarks section. This monograph is a beautiful introduction to this (at this moment unsolved) problem.