1
$\begingroup$

There is a list of 3-dimensional points $(x_1,y_1,z_1),\ldots,(x_m, y_m,z_m)$, where all coordinates are non-zero integers.

I would like to decide whether there exist positive real weights $w_x, w_y, w_z$ such that, for all $i$ in $1,\ldots,m$, $$ (*) ~~~~~~~~~~~~~~ w_x x_i + w_y y_i + w_z z_i \geq 0. $$


Here is an algorithm that solves a similar problem in two dimensions (i.e., assuming $z_i=0$ for all $i$).

  1. If $x_i<0$ and $y_i<0$ for some $i$, then no positive weights satisfy (*) for this $i$; return "no".

  2. If $x_i>0$ and $y_i>0$ for some $i$, then all positive weights satisfy (*) for this $i$; remove this pair from the list.

  3. In the remaining pairs, either $x_i>0$ and $y_i<0$, or $x_i<0$ and $y_i>0$. Denote the pairs of the former type by $A_x$ and the pairs of the latter type by $A_y$.

  • For all pairs in $A_x$, (*) is equivalent to: $-y_i/x_i \leq w_x/w_y$;
  • For all pairs in $A_y$, (*) is equivalent to: $-y_i/x_i \geq w_x/w_y$.

In other words, the weights $w_x,w_y$ satisfy (*) if and only if their ratio $w_x/w_y$ is in the following range: $$ \left[ \max_{i\in A_x} (-y_i/x_i), \ldots, \min_{i\in A_y} (-y_i/x_i) \right] $$

If this range is empty, then return "no". Otherwise (that is, $ \max_{i\in A_x} (-y_i/x_i) \leq \min_{i\in A_y} (-y_i/x_i) $), return any weights $w_x,w_y$ whose ratio is in this range.

The algorithm requires O(poly(m)) arithmetic operations.


QUESTION: Is there an algorithm for solving the original, 3-dimensional problem, using O(poly(m)) arithmetic operations?

$\endgroup$

2 Answers 2

2
$\begingroup$

In general, constant-dimension LP can be solved in a strongly polynomial time.

The easiest way is just trying all vertices. A vertex is determined by $3$ half-planes (inequalities including the non-negativity constraints). Running a Gaussian elimination on a candidate set of half-planes will give a point if the half-planes are independent. Then, check the point against all inequalities.

There are at most $\binom{m + 3}{3}$ vertices, and $O(m^4)$ arithmetic operations are required.

It is possible to do it more efficiently. Randomized algorithms for LP-type_problem run in a linear time for a fixed dimension.

$\endgroup$
1
$\begingroup$

It can be solved in time polynomial in the length of the input. This is an instance of linear programming, in 3 unknowns. Linear programming can be solved in polynomial time when the dimension is fixed. This doesn't answer whether or not it can be solved in O(poly(m)) arithmetic operations.

$\endgroup$
2
  • $\begingroup$ If I understand the link correctly, it says that LP is linear in the number of bits in the input ("weakly polynomial"). But the algorithm I described for the two-dimensional case is polynomial in $m$ only - the number of arithmetic operations does not depend on the number of bits ("strongly polynomial"). $\endgroup$ Jul 23 at 20:52
  • $\begingroup$ @ErelSegal-Halevi, good point! Thank you for correcting my oversight. $\endgroup$
    – D.W.
    Jul 23 at 22:09

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.