Given a set of 2D vectors, find the furthest reachable point

Question

Input: a set of 2D vectors $S=\{v_1,v_2,\dots,v_n\mid v_i\in \mathbb{Z}^2 \}$
Question: name $P=\{\sum_{v_i\in S'}v_i\mid S'\subseteq S \}$ for all subsets of $S$ (obviously $|P|=O(2^n)$). In words, $P$ is the set of all possible vectors we can form by adding vectors from $S$.
What is the length of the longest vector in $P$?

An idea:
(An easy observation is that if all $v_i\in S$ are in one orthant (or quadrant?) we just have to add them. If the vectors are in on hyperplane this is not true.) Start from an arbitrary vector $v_1\in S$, get the next one $v_2$ (either left or right) and add $V=v_1+v_2$. Generally, at each step $V=V+v_i$. Continue this while $|V|$ is increasing.

At some time we find $v_j$ such that $V=V+v_j$ shortens. Set $V=V-v_1+v_j$ and continue. The idea is to maintain a "window" where we add all the vectors inside. If the next vector (the one side of the window) does not add, remove the first one (the other side of hte window).

I know I am not clear enough but hope you get the idea.

Is this correct? Am not sure...
An other ideas/approaches?

(This, of course, can be generalized to any dimension $k$. I mentioned the 2D case because it is easy to visualize.)

I am looking for algorithms with polynomial time on $n=|S|$.

Related problem: lattice problems.

Let set $S$ be the basis of the lattice $L$. Then $L$ is defined as $$L(S)=\{\sum_{i=1}^{n}a_i v_i \mid v_i\in S, a_i\in\mathbb{Z}\} $$

Our set $P$ is a special case if, instead of $a_i\in\mathbb{Z}$ we let $a_i\in \{0,1\}$.

Answer 1

Suppose you knew the direction $\hat{d}$ of a longest vector sum. Then finding a subset of vectors that should be included in the longest-vector sum is trivial:

• Include $v$ when the dot product $v \cdot \hat{d} > 0$.
• Exclude $v$ when $v \cdot \hat{d} < 0$.
• There won't be a $v$ where $v \cdot \hat{d} = 0$, unless $v=0$, because that contradicts $\hat{d}$ pointing towards a longest vector sum.

Now consider what happens if we vary $\hat{d}$ away from the optimal direction to get $d^\prime$. The sum-along-directions stays constant... until we turn so much that one of the dot products $v \cdot d^\prime$ switches sign. That only happens when $d^\prime$ is perpendicular to a $v$.

Since we're working in 2-d, we can think in terms of angles instead of directions. We have a function $f(\theta)$ that adds up all vectors $v$ even-slightly-aligned with the angle $\theta$. And we know this function only changes values when $\theta$ is perpendicular to one of the vectors $v$. And we know there are at most $2n$ such critical angles.

Ah.

Algorithm

Make a list of all the critical angles where $f(\theta)$'s value changes due to $\theta$ being perpendicular to a $v$. Sort the list. Find a maximizing $\theta$ by sampling $f$ at the midpoint between each contiguous pair of critical points (remembering to include the midpoint where the angles wrap around). Use that $\theta$ to recover a best set of vectors.

By adjusting the total as vectors cross in and out of alignment, instead of recomputing it every time, the algorithm will run in time $O(n \log n)$ with the most expensive step being the sorting of the critical points.

Here's some quick and dirty pseudo-code. WARNING: THIS CODE WAS WRITTEN BY HAND WITHOUT BEING RUN OR TESTED. IT WILL CONTAIN BUGS.

import math


def dot(u, v):
    return u[0]*v[0] + u[1]*v[1]


def vec_sum(vecs):
    t = [0, 0]
    for v in vecs:
        t[0] += v[0]
        t[1] += v[1]
    return tuple(t)


def vectors_along(vec_set, angle):
    d = (math.cos(angle), math.sin(angle))
    return [v for v in vec_set if dot(d, v) > 0]


def transitions(vecs):
    # compute (critical-angle, vector, entering-vs-leaving) tuples
    results = [(t % (2*math.pi), v, b)
               for v in vecs
               for (t, b) in [(math.atan2(v[0], -v[1]), True),
                              (math.atan2(-v[0], v[1]), False)]]
    return sorted(results, key=lambda e: e[0])


def longest_subset(vecs):
    best_angle = None
    current_total_vec = None
    best_norm = 0
    for transition, vec, entering in transitions(vecs):
        # TODO: If two transitions are less than 0.00001 apart this fails
        # TODO: In particular, equal/opposite vectors cause equal transitions.
        angle = transition + 0.00001
        if current_total_vec is None:
            current_total_vec = vec_sum(vectors_along(vecs, angle))
        else:
            current_total_vec += vec * (1 if entering else -1)
        current_norm = dot(current_total_vec, current_total_vec)
        if current_norm > best_norm:
            best_norm = current_norm
            best_angle = angle
    return vectors_along(vecs, best_angle)

Higher Dimensions

This idea works quickly in 2d, but in 3d the boundaries that add/remove a vector from the along-direction sets are great circles instead of points. So everything gets more complicated and more expensive there and continues to get more complicated as you go to higher dimensions.

Answer 2

This problem appears on the competitive programming contest here:

https://szkopul.edu.pl/problemset/problem/NZSCUwz2ACePsBKuVCIVzrRt/site/?key=statement

Apparently it's the Polish Olympiad in Informatics 2018.

The problem has $n \le 200,000$ vectors, meaning that any brute force solution won't work.

I solved this problem in $O(N \log N)$ with a polar sort, so I'll share how I did it. Assume we start at $(0, 0)$.

1. Polar sort all vectors $O(N \log N)$
2. Traverse all vectors in $O(N)$ and do the following with Two-Pointers:

long long calculate(const vector<Point>& points) {
  Point curr{0, 0};
  long long ans = 0;

  for (int i = 0, j = 0; i < (int)points.size(); i++) {
    curr = curr + points[i]; // vector addition

    while (j < i) {
      const long long new_dist = (curr - points[j]).magnitude();

      if (new_dist > curr.magnitude()) {
        curr = curr - points[j];
        j++;
      } else {
        break;
      }
    }

    ans = max(ans, curr.magnitude());
  }

  return ans;
}

In this case, magnitude is the squared distance, so it's always an integer. Either apply square root afterwards or keep it like that, whatever you need.

In my implementation, I had to do 4 polar sorts in total. I assume this is because the code misses some corner case.

long long a, b, c, d;

sort(points.begin(), points.end());
a = calculate(points);

reverse(points.begin(), points.end());
b = calculate(points);

// Reflect the X coordinate, so that
// the next polar sort sorts the points differently (?)
for (Point& p : points) p.x *= -1;

sort(points.begin(), points.end());
c = calculate(points);

reverse(points.begin(), points.end());
d = calculate(points);

// Final answer
cout << max({a, b, c, d}) << endl;

Observation: The subset of vectors chosen (in the optimal solution) is always a subarray of the polar sorted vectors, in other words, the vectors are contiguous. I verified this with brute force as well (by traversing all subsets in $O(2^n)$).

Answer 3

The complexity of your problems depends on whether the vectors are represented in unary or binary.

Unary

If the vectors are represented in unary, all of the problems you mention can be solved in polynomial time using dynamic programming.

You introduce an array $A[\cdot,\cdot,\cdot]$ where $A[k,x,y]=1$ if there's a subset of $v_1,\dots,v_k$ that sums to the vector $(x,y)$; the array has polynomial size, and can be filled in in polynomial time. Then by iterating over the entries of $A[n,\cdot,\cdot]$, you can find the shortest vector, the longest vector, the closest vector to any other desired vector, and the convex hull.

Binary

If your vectors are represented in binary, the shortest vector problem is NP-hard by a reduction from subset sum. Given integers $x_1,\dots,x_n$, we form two-dimensional vectors by $v_i=(x_i,0)$. Then the shortest vector in $P$ has length 0 if and only if there is a subset of $x_i$'s that sum to zero. Thus, if you had an efficient algorithm for your shortest vector problem, you could solve subset sum efficiently. Since subset sum is NP-complete, it follows that you're unlikely to be able to find an efficient algorithm for the shortest vector problem you describe.

I don't know what the complexity of the longest vector problem is, but I suspect you might be able to find a reduction from some other NP-hard problem (e.g., something knapsack-related).