An iterative algorithm for finding a nearest pair of points in two convex subsets of Rn

✍ Scribed by B. Llanas; M. Fernandez de Sevilla; V. Feliu

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 536 KB
• Volume: 40
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/s0898-1221(00)85008-7

✦ Synopsis

We present an algorithm for finding a nearest pair of points in two convex sets of R n, and therefore, their distance. The algorithm is based on the fixed-point theory of nonexpansive operators on a Hilbert space. Its practical implementation requires a fast projection algorithm. We introduce such a procedure for convex polyhedra. This algorithm effects a local search in the faces using visibility as a guide for finding the global minimum. After studying the convergence of both algorithms, we detail computer experiments on polyhedra (projection and distance). In the case of distances, these experiments show a sublinear time complexity relative to the total number of vertices.