Median hyperplanes in normed spaces - a survey

In this survey we deal with the location of hyperplanes in n-dimensional no rmed spaces, i.e., we present all known results and a unifying approach to the so-called median hyperplane problem in Minkowski spaces. We describe ho w to find a hyperplane H minimizing the weighted sum f(H) of distances to a given, finite set of demand points. In robust statistics and operations re search such an optimal hyperplane is called a median hyperplane. After summ arizing the known results for the Euclidean and rectangular situation, we s how that for all distance measures d derived from norms one of the hyperpla nes minimizing f(H) is the affine hull of n of the demand points and, moreo ver, that each median hyperplane is a halving one tin a sense defined below ) with respect to the given point set. Also an independence of norm result for finding optimal hyperplanes with fixed slope will be given. Furthermore , we discuss how these geometric criteria can be used for algorithmical app roaches to median hyperplanes, with an extra discussion for the case of pol yhedral norms. And finally a characterization of all smooth norms by a shar pened incidence criterion for median hyperplanes is mentioned. (C) 1998 Els evier Science B.V. All rights reserved.