Can this algorithm for 2-dimensional points be generalized to 3 dimensions?

Question

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?

Answer 1

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.

Answer 2

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.