Median and center hyperplanes in Minkowski spaces—a unified approach

AbstractIn this paper we will extend two known location problems from Euclidean n-space to all n-dimensional normed spaces, n⩾2. Let X be a finite set of weighted points whose affine hull is n-dimensional. Our first objective is to find a hyperplane minimizing (among all hyperplanes) the sum of weighted distances with respect to X. Such a hyperplane is called a median hyperplane with respect to X, and we will show that for all distance measures d derived from norms one of the median hyperplanes is the affine hull of n of the demand points. (This approach was already presented in the recent survey (Discrete Appl. Math. 89 (1998) 181), but without proofs. Here we give the complete proofs to all necessary lemmas.) On the other hand, we will prove that one of the hyperplanes minimizing (among all hyperplanes) the maximum weighted distance to some point from X has the same maximal distance to least n+1 affinely independent demand points (such a hyperplane is said to be a center hyperplane of X). Both these results allow polynomially bounded algorithmical approaches to median and center hyperplanes and the respective distance sums or maximal distances for any fixed dimension n⩾2, and in particular we discuss the algorithms for both the problems in the case of polyhedral norms. Also two independence of norm results for optimal hyperplanes with fixed slope will be derived, and finally the considerations are even extended to gauges which are no longer combined with a norm