Approximate Search for the kth Order Distance in a System of Unit Square Points

For a given tuple P=(p₁,,pₙ) (a set of points of the unit square) and a number 1≤ k≤ n2 , this paper considers the problem of finding the k th ordinal distance between elements of P in the ₛ -norm, where s∈\1,∞\ . In other words, we consider the problem of finding a minimal dₖ such that ∑_i 0 , we propose an ε -approximation algorithm with complexity O(nlog nlog(1/ε)) for computing dₖ .