next up previous
Next: Problem 42: Vertex-Unfolding Polyhedra Up: The Open Problems Project Previous: Problem 40: The Number

Problem 41: Sorting X + Y (Pairwise Sums)

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 | xX, yY}.

The earliest known reference is Fredman [Fre76], who attributes the problem to Elwyn Berlekamp.
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(n2log n)-time algorithm is also the fastest known. There are Ω(n2) 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 log2L + 2m comparisons. For the sorting X + Y problem, we have m = n2, the Hasse diagram of the partial order is an n×n diagonal grid, and simple arguments about hyperplane arrangements imply that L = O(n8n). Thus, Fredman's algorithm can sort X + Y using only 8n log n + 2n2 comparisons; unfortunately, the algorithm needs exponential time to choose which comparisons to perform! This exponential overhead was reduced to polynomial time by Kahn and Kim [KK95] and then to O(n2log 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 Ω(n2) 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 n2 unique elements?--is 3SUM-hard [BHP01]; see Problem 11.
lower bounds
Entry Revision History
E. Demaine, 6 June 2002; Jeff Erickson, 20 June 2002; J. O'Rourke, 20 Aug. 2006.


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

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.

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.

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

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

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

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

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

Jean-Luc Lambert.
Sorting the sums (xi + yj) in O(n2) comparisons.
Theoret. Comput. Sci., 103:137-141, 1992.

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

next up previous
Next: Problem 42: Vertex-Unfolding Polyhedra Up: The Open Problems Project Previous: Problem 40: The Number
The Open Problems Project - December 04, 2015