Next: Problem 42: Vertex-Unfolding Polyhedra
Previous: Problem 40: The Number of Pointed Pseudotriangulations
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 \mid x \in X, y \in Y\}.
The earliest known reference is Fredman [Fre76], who attributes the problem to Elwyn Berlekamp.
Open.
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 \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].
The obvious O(n^2 \log n)-time algorithm is also the fastest known. There are \Omega(n^2) 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_2 L + 2m comparisons. For the sorting X+Y problem, we have m = n^2, the Hasse diagram of the partial order is an n\times n diagonal grid, and simple arguments about hyperplane arrangements imply that L = O(n^{8n}). Thus, Fredman’s algorithm can sort X+Y using only 8n\log n + 2n^2 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(n^2\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^2) 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.
The decision version of this problem—does the set X+Y have n^2 unique elements?—is 3SUM-hard [BHP01]; see Problem 11.
lower bounds
E. Demaine, 6 June 2002; Jeff Erickson, 20 June 2002; J. O’Rourke, 20 Aug. 2006.
A. Hernández Barrera. Finding an o(n^2 \log 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. . In Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006), pages 160–171, 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 (x_i+y_j) in O(n^2) 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.