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

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?

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.

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.

• 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"). Jul 23 at 20:52
• @ErelSegal-Halevi, good point! Thank you for correcting my oversight.
– D.W.
Jul 23 at 22:09