← All problems

Sorting X+YX+Y (Pairwise Sums)

50 years old · documented by

Let n≥1n\geq 1, and let XX and YY be sets of nn numbers in a linearly ordered domain. The question is to sort their pairwise sums. In the usual algorithmic formulation, the items to be sorted are indexed by pairs, so repeated values are retained:

(x+y)(x,y)∈X×Y,(x+y)_{(x,y)\in X\times Y},

with output in nondecreasing order. The literal set

X+Y={x+y:x∈X, y∈Y}X+Y=\{x+y:x\in X,\ y\in Y\}

contains only distinct values; it can be obtained from the sorted list by deleting repetitions. The central complexity question is the worst-case running time, particularly in the comparison model, for sorting these sums. The standard comparison-based bounds treat the n2n^2 pair-indexed sums as the items. Open Problems Project, Problem 41

Background

This problem is a structured instance of sorting with partial information: the input sums are not arbitrary, because sorting XX and YY imposes a grid-shaped partial order on the pair-indexed sums. Fredman’s 1976 paper is the earliest known reference; it attributes the problem to Elwyn Berlekamp. The question also matters as a source of reductions: sorting X+YX+Y is a hardness benchmark for several geometric problems, including computing Minkowski sums of orthogonal-convex polygons, sorting vertices of a line arrangement, and sorting interpoint distances. Fredman also noted an application to multiplying sparse polynomials. Open Problems Project, Problem 41 Fredman (1976) Hernández Barrera (1996) Barequet and Har-Peled (2001)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.