Thesis Committe: Dr. William Steiger, Dr. Michael Fredman, Dr. Endre Szemeredi

Abstract:

The set of Cartesian sums of two vectors X and Y, each of length n, is the set {Xi + Yj | Xi is an element of X, Yj is an element of Y}. The n^2 elements of this set obey an extensive partial order, and for this reason, the sorting of Cartesian sums is a commonly studied example of the general problem of sorting a set with partial ordering information initially available. Fredman showed that when sorting consists of selecting from among P possible total orderings on a set of m elements, it may be done using no more than log|P| + 2m comparisons between elements of the set. Furthermore, the Cartesian sums of two n-element vectors may be ordered in no more than n^8n ways, and may be sorted with O(n^2) comparisons in the worst case. Lambert and later Steiger and Streinu developed algorithms which accomplished the task using O(n^2) comparisons (but more than O(n^2) work overall) in the worst case. We examine two special cases of Cartesian sums, and describe algorithms that sort such sets using O(n^2) work. In the first special case, we constrain one of the source vectors, from which the Cartesian sums are produced, to be an arithmetic sequence. In the second special case, we constrain one of the source vectors to be a geometric sequence with a fixed ratio. In both cases, our algorithms exploit the fact that the relative ordering of all elements in certain subsets of the set of Cartesian sums, of size 2n, can be determined in constant time. Finally, we suggest how the approach used herein may provide the basis for work on more general cases of the problem.