Selecting the K th Element in $X + Y$ and X₁ + X₂ + ⋯ + Xₘ

An algorithm is given which selects the Kth element in $X + Y$ in O(nlog n) time and $O(n)$ space, where $X + Y$ is the multiset \ xᵢ + yⱼ | xᵢ ∈ X and yⱼ ∈ Y\ for X = (x₁ ,x₂ , ⋯ ,xₙ ) and Y = (y₁ ,y₂ , ⋯ ,yₙ ), n-tuples of real numbers. The results are extended to ∑i = 1ᵐ Xᵢ for $m > 2$. There is strong evidence that this more general problem is difficult if m and K may be selected arbitrarily. However, algorithms can be shown which are fast for small K and arbitrary m.