On the distance between polytopes
This paper is written to fill an apparent gap in the literature in connection with some elementary problems of distance in finite dimensional normed linear spaces. In particular the problem of determining the distance between two polytopes in a normed n-dimensional real vector space is considered. Special consideration is given to the case in which the norm is a twice differentiable function of its arguments and for this case a convex programming algorithm is presented. In addition several other cases are considered including the well known discrete Tchebycheff approximation. The results should find application in approximation theory. 0. Notation. Rn —The vector space of all real n-tuples {ax , ■ ■ ■ , an)T 11 •11 —A norm on R" |, —The norms defined by imi. = (i:w),/ for 1 < t < oo ||f/||oo = max \ui\ U t Ii" i R"t ■—The normed linear space \Rn, ||-||i} e -—The vector (1,1, • • • , 1 )T t R" A+ —The Moore-Penrose inverse of a matrix A, or generalized inverse of A, see [7].