L-infinity interdistance selection by parametric search (Q1115620)

The selection problem asks for the kth largest or smallest element in a set S. In general, selection takes linear time, but if the set is constrained so that some relations between elements are known, sublinear- time selection is sometimes possible. We present an algorithm that selects the kth largest or smallest element from a Cartesian sum in O(n log n) time and extend this result to select \(L_{\infty}\)- interdistances in \({\mathbb{R}}^ d\) in O(d n \(log^{d-1} n)\) time. The algorithm is based on a general technique of Megiddo and improved by Cole, and it is the first algorithm for a multidimensional interdistance selection problem with an O(n \(log^{O(1)}n)\) running time.