Proximity problems deal with "closeness" of points in a finite set in k-dimensional space under some distance metric L (subscript p). These problems arise in many applications such as pattern recognition, wire routing, and ...