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. NEWLINENEWLINENEWLINELet \(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. NEWLINENEWLINENEWLINEIn 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. NEWLINENEWLINENEWLINEBoth 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. NEWLINENEWLINENEWLINEAt 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. NEWLINENEWLINENEWLINEIn 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.