Median and center hyperplanes in Minkowski spaces -- a unified approach (Q5951951)

The authors extend two location problems from Euclidean \(n\)-space to all \(n\)-dimensional normed spaces. The first problem is the question for a median hyperplane, the second one asks for a center hyperplane. Let \(X\) be a finite set of \(m\) weighted points whose affine hull is \(n\)-dimensional. A median hyperplane is a hyperplane which minimizes the sum of weighted distances with respect to \(X\). The hyperplane minimizing the maximum weighted distance to some point from \(X\) is called a center hyperplane. In this note the generalization for Minkowski spaces is formulated by Theorem 3: (i) There exists a median hyperplane with respect to \(X\) which is spanned by \(n\) affinely independent points from \(X\), and each median hyperplane is a pseudo-halving one. (ii) There exists a center hyperplane which is at maximum distance from \(n+1\) affinely independent points from X. Both these results allow polynomially bounded algorithmical approaches to median and center hyperplanes and to the respective distance sums or maximal distances for any fixed dimension \(n \geq 2\). In the case of polyhedral norms an algorithm for both problems is presented. It runs in O\((rm)\) time, where \(2r\) is the number of extrem points of the corresponding polytope. At the end, more generally, some considerations are extended to gauges, where the symmetry property of the distance function is not required. Here, besides general statements, one special result for dimension two can be given. In this paper the authors describe former results in this field and give a long detailed list of references. Especially they mention their unproofed results of a survey [Discrete Appl. Math. 89, 181-195 (1998; Zbl 0921.90109)] and now they give the corresponding complete proofs.