Problem 41: Sorting X + Y (Pairwise Sums)

Statement

Given two sets of numbers, each of size n, how quickly can the set of all pairwise sums be sorted? In symbols, given two sets X and Y, our goal is to sort the set

X + Y = {x + y | x $$\in$$ X, y $$\in$$ Y}.

Origin

The earliest known reference is Fredman [Fre76], who attributes the problem to Elwyn Berlekamp.

Status/Conjectures

Open.

Motivation

This is a simple special case of the more general question of sorting with partial information: How many comparisons are required to sort if a partial order on the input set is already known? Hernández Barrera [Her96] and Barequet and Har-Peled [BHP01] describe several geometric problems that are ``Sorting-(X + Y)-hard''. Specifically, there is a subquadratic-time transformation from sorting X + Y to each of the following problems: computing the Minkowski sum of two orthogonal-convex polygons, determining whether one monotone polygon can be translated to fit inside another, determining whether one convex polygon can be rotated to fit inside another, sorting the vertices of a line arrangement, or sorting the interpoint distances between n points in $\mathbb {R}$^d. (Although Barequet and Har-Peled [BHP01] claim only that the problems they consider are 3SUM-hard, their proofs immediately imply this stronger result.) Fredman also mentions an immediate application to multiplying sparse polynomials [Fre76].

Partial and Related Results

The obvious O(n²log n)-time algorithm is also the fastest known. There are $\Omega$(n²) lower bounds for this problem in various restrictions of the linear decision tree model of computation [Fre76,Die89,Eri99a]. The main problem is whether the logarithmic factor can be removed.

Fredman [Fre76] proved that if a given partial order on m elements has L linear extensions, then the set can be sorted in at most log₂L + 2m comparisons. For the sorting X + Y problem, we have m = n², the Hasse diagram of the partial order is an n×n diagonal grid, and simple arguments about hyperplane arrangments imply that L = O(n⁸ⁿ). Thus, Fredman's algorithm can sort X + Y using only 8n log n + 2n² comparisons; unfortunately, the algorithm needs expoonential time to choose which comparisons to perform! This exponential overhead was reduced to polynomial time by Kahn and Kim [KK95] and then to O(n²log n) by Lambert [Lam92] and Steiger and Streinu [SS95]. These results imply that no superquadratic lower bound is possible in the full linear decision tree model.

If the input consists of n integers between - M and M, an algorithm of Seidel based on fast Fourier transforms runs in O(n + M log M) time [Eri99a]. The $\Omega$(n²) lower bounds require exponentially large integers.

A closely related problem does have a subquadratic solution: find a minimum element of X + Y, the so-called min-convolution problem, posed by Jeff Erickson [DO06]. See [BCD+06] for the result and a discussion of connections to the sorting problem.

Related Open Problems

The decision version of this problem--does the set X + Y have n² unique elements?--is 3SUM-hard [BHP01]; see Problem 11.

Categories

lower bounds

Entry Revision History

E. Demaine, 6 June 2002; Jeff Erickson, 20 June 2002; J. O'Rourke, 20 Aug. 2006.

Bibliography

Her96

A. Hernández Barrera.
Finding an o(n²log n) algorithm is sometimes hard.
In Proc. 8th Canad. Conf. Comput. Geom., pages 289-294. Carleton University Press, Ottawa, Canada, 1996.

BCD+06

David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, and Perouz Taslakian.
Necklaces, convolutions, and X + Y.
In Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006), page to appear, Zürich, Switzerland, September 11-13 2006.

BHP01

G. Barequet and S. Har-Peled.
Polygon containment and translational min-Hausdorff-distance between segment sets are 3SUM-hard.
Internat. J. Comput. Geom. Appl., 11:465-474, 2001.

Die89

M. Dietzfelbinger.
Lower bounds for sorting of sums.
Theoret. Comput. Sci., 66:137-155, 1989.

DO06

Erik D. Demaine and Joseph O'Rourke.
Open problems from CCCG 2005.
In Proc. 18th Canad. Conf. Comput. Geom., pages 75-80, 2006.

Eri99a

Jeff Erickson.
Lower bounds for linear satisfiability problems.
Chicago J. Theoret. Comput. Sci., 1999(8), 1999.

Fre76

M. L. Fredman.
How good is the information theory bound in sorting?
Theoret. Comput. Sci., 1:355-361, 1976.

KK95

Jeff Kahn and Jeong Han Kim.
Entropy and sorting.
J. Comput. Sys. Sci., 51:390-399, 1995.

Lam92

Jean-Luc Lambert.
Sorting the sums (x_i + y_j) in O(n²) comparisons.
Theoret. Comput. Sci., 103:137-141, 1992.

SS95

W. Steiger and Ileana Streinu.
A pseudo-algorithmic separation of lines from pseudo-lines.
Inform. Process. Lett., 53:295-299, 1995.