The Open Problems Project

Next: Problem 42: Vertex-Unfolding Polyhedra

Previous: Problem 40: The Number of Pointed Pseudotriangulations

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 \mid 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 \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^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.

Related Open Problems

The decision version of this problem—does the set X+Y have n^2 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^2 \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. . In Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006), pages 160–171, 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^2) 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.