2
$\begingroup$

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\}$.

$\endgroup$
  • $\begingroup$ Have you tried thinking about the 1-dimensional case? Perhaps from there you can find a solution for higher dimensions. $\endgroup$ – adrianN Apr 19 '16 at 12:47
  • $\begingroup$ Related question. $\endgroup$ – Raphael Apr 19 '16 at 13:06
  • 1
    $\begingroup$ Related, well-studied problem. $\endgroup$ – Raphael Apr 19 '16 at 13:07
  • $\begingroup$ @Raphael, you are right about the title. It baffled me too. I changed it to something, hopefully, better understandable. $P=2^n$ at the worst case, of course there can be vector sums that add to the same point. Edited that too. The stack question does not seem relevant to me. The Maximum subarray problem may be related. I will have a look although I believe they are not the same. Thanks for the feedback and the info. $\endgroup$ – Harry Apr 19 '16 at 16:38
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think I get what you say, not sure yet. Why are there $2n$ critical angles and not $n$? The critical angles are those between vectors? I will see it thoroughly at some point, just do not have the time now. Thanks. $\endgroup$ – Harry Jun 3 '16 at 15:06
  • $\begingroup$ @Harry a vector defines two critical angles because there's two directions perpendicular to the vector. If the vector of pointing up then the two perpendicular directions are leftward and rightward. $\endgroup$ – Craig Gidney Jun 3 '16 at 15:09
0
$\begingroup$

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).

$\endgroup$
  • 2
    $\begingroup$ I believe you are right about the shortest vector problem. An also related problem (actually the same) is the Minkowski Decomposition that is NP-hard even for dimension 2. But for the longest I suspect that there is a quadratic or even linear time algorithm. The key observation should be (if it correct) that the vectors added to form the longest vector must be consequtive whereas for the shortest vector this is not necessary. Bot I am not sure about the correcteness of this observation!! $\endgroup$ – Harry Apr 19 '16 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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