An iterative algorithm for finding a nearest pair of points in two convex subsets of R-n

We present an algorithm for finding a nearest pair of points in two convex sets of Rn, and therefore, their distance. The algorithm is based on the fi xed-point theory of nonexpansive operators on a Hilbert space. Its practica l implementation requires a fast projection algorithm. We introduce such a procedure for convex polyhedra. This algorithm effects a local search in th e faces using visibility as a guide for finding the global minimum. After s tudying the convergence of both algorithms, we detail computer experiments on polyhedra (projection and distance). In the case of distances, these exp eriments show a sublinear time complexity relative to the total number of v ertices. (C) 2000 Elsevier Science Ltd. All rights reserved.