L-infinity interdistance selection by parametric search
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.
multidimensional interdistance selection
scientific article; zbMATH DE number 4087036
scientific article