2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Commented Nov 20, 2018 at 2:24
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Nov 20, 2018 at 2:29
  • $\begingroup$ @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... $\endgroup$ Commented Nov 20, 2018 at 4:40
  • $\begingroup$ @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. $\endgroup$ Commented Nov 20, 2018 at 4:43
  • $\begingroup$ 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$. $\endgroup$ Commented Nov 20, 2018 at 16:14

1 Answer 1

2
$\begingroup$

Observations:

  1. The pairing mechanism creates the Minkowski sum of the two sets.
  2. The convex hull of the Minkowski sum is the Minkowski sum of the convex hulls. (See e.g. previously linked Wikipedia article).
  3. Given a set of points in the plane, the point furthest from the origin must be a vertex of the convex hull.
  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...

    given in the Wikipedia article.

Combining these observations gives an $O(n \lg n)$ algorithm.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.