# Find pair of complex numbers with maximal sum

Given two lists of complex numbers, is there an efficient algorithm to choose one element from each list such that the magnitude of their sum is maximal?

• Have you made any progress towards this problem? Have you tried solving any special cases of this problem? For instance, have you tried solving the special case where all complex numbers have magnitude 1?
– D.W.
Commented Nov 20, 2018 at 2:24
• A possible line of attack: call the two lists $L_1,L_2$. Randomly sample a subset $S$ of $\sqrt{n}$ of the numbers from $L_1$. Project each element of $L_1$ onto each element of $S$; for each $s \in S$ let $f(s)$ be the element in $L_1$ whose projection onto $s$ has maximal magnitude. For each $s \in S, y \in L_2$, look at the magnitude $|f(s)+y|$ as an approximation for $|x+y|$ for all points $x \in L_1$ whose angle is similar to $s$. Then do something to deal with the errors that the projection approximation introduces (somehow ???), and hope this leads to an $O(n^{1.5})$ time algorithm.
– D.W.
Commented Nov 20, 2018 at 2:29
• @D.W. That seems promising. Another line of attack I've considered is the following. Conjecture: if the pair with largest sum is $(a,b)$, then $b$ is $a$'s nearest neighbor. So we can construct a KD-tree (thinking of the numbers as 2-vectors), find each point's nearest neighbor in time $O(n \log n)$, and then test each resulting pair. But I'm not sure if the conjecture is valid... Commented Nov 20, 2018 at 4:40
• @D.W. Motivation for the conjecture: $|a+b| = |2a + (b-a)| \leq |2a| + |b-a|$, which is minimized when $b$ is $a$'s nearest neighbor. But it's only an upper bound, so the conjecture could still be false. Commented Nov 20, 2018 at 4:43
• Counterexample to the conjecture: first set is $\{1\}$, second set is $\{0, i\}$. The nearest neighbour of $1$ is $0$, but the largest sum is $1+i$. Commented Nov 20, 2018 at 16:14

4. The convex hull of a set of $$n$$ points can be found in $$O(n \lg n)$$ time. (In fact in $$O(n \lg h)$$ time, where $$h$$ is the number of points on the convex hull).
5. For two convex polygons P and Q in the plane with $$m$$ and $$n$$ vertices, their Minkowski sum is a convex polygon with at most $$m + n$$ vertices and may be computed in time $$O(m + n)$$ by a very simple procedure...
Combining these observations gives an $$O(n \lg n)$$ algorithm.