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

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

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 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.
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(n2log 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 (xi + yj) in O(n2) 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.

Next: Problem 42: Vertex-Unfolding Polyhedra Up: The Open Problems Project Previous: Problem 40: The Number
The Open Problems Project - September 19, 2017