Given a set of n inequalities each of the form ax+by+cz≤d for some a,b,c,d in Q, determine if there

shelohz0 2022-05-20 Answered
Given a set of n inequalities each of the form ax+by+cz≤d for some a,b,c,d in Q, determine if there exists x, y and z in Q that satisfy all the inequalities.
Here is an O(n4) algorithm for solving this: for each triple of inequalities, intersect their corresponding planes to get a point (x,y,z) iff possible. If no such intersecting point exists continue on to the next triple of inequalities. Test each of these intersection points against all the inequalities. If a particular point satisfies all the inequalities the solution has been found. If none of these points satisfy all the inequalities then there is no point satisfying the system of inequalities. There are O(n3) such intersection points and there are n inequalities thus the algorithm is O(n4).
I would like a faster algorithm for solving this (eg: O(n3), O(n2), O(n*logn), O(n)). If you can provide such an algorithm in an answer that would be great. You may notice this problem is a subset of the more general k-dimensional problem where there are points in k-dimensions instead of 3 dimensions as in this problem or 2 dimensions as in my previous problem mentioned above. The time complexity of my algorithm generalized to k dimensions is O(nk+1). Ideally I would like something that is a polynomial time algorithm however any improvements over my naive algorithm would be great. Thanks
You can still ask an expert for help

Want to know more about Inequalities systems and graphs?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

zwichtsu
Answered 2022-05-21 Author has 9 answers
You can modify your algorithm a bit to make it O ( n 3 ).
If we have a line, we can check if there's a point on that line satisfying all inequalities in O ( n ) time. If we denote one of the directions on this line "up", each plane gives you an upper or lower bound on the part of the line satisfying the inequalities. So we can compute the intersection points between the line and each plane, and check if the lowest upper bound is above the highest lower bound.
Like in your algorithm, candidate lines can be intersection lines between each pair of planes O ( n 2 ) of them. So you get a total complexity of O ( n 3 ).
Note, care must be taken for the special case when all planes are parallel and so there's no intersection lines.
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2022-08-01
7 x x 2 + 2 x y + y  + 3 x x 2 + x y = 0
asked 2021-08-17
5y=160+9x
Find the slope of the line.
asked 2021-11-17
To fill: The bla

70qt= gal qt
asked 2021-12-03
Find the quadratic function that is best fit for f(x) defined by the table below
Xf(x)0024014159863595864071010,009
The quadratic function is y=.
(Type an equation using as the variable. Round to two decimals places as needed)
asked 2022-02-22
Suppose the 4-vector c gives the coefficients of a cubic polynomial p(x)=c1+c2x+c3c2+c4c3. Express the conditions
p(1)=p(2),p(1)=p(2)
as a set of linear equations of the form Ac=b. Give the sizes of A and b, as well as their entries.
So far, what I've done was sub in the values and differentiate the polynomials and let it equal to each other after subbing their values.
I get
c1+c2+c3+c4=c1+2c2+4c3+8c4
then,
0=c2+3c3+7c4
as well as
c2+2c3+3c4=c2+4c3+12c4
then,
0=2c3+9c4
What should I do now?
asked 2022-03-30
asked 2022-02-24
I already know how the set of solutions of system of linear equations over real numbers infinite field PP is expressed.
When there is only single solution then it is just a vector of scalars, where each scalar is a real number.
When there are more than 1 solution, and actually infinite solutions, then it is just a parametric linear vector space in the form: tR:p+vt where pRnlandvRn where n denotes the number of real variables in each linear equation thus nN
But my question is how the set of solutions of system of linear equations over the finite field Z2 or galois field GF(2) is expressed?
I already know that when there is only single solution then it is also just a vector of scalars, but where each scalar is a binary number either zero or one in Z2 where Z2={0,1}, but when there are more than 1 solution, but always finite number of solutions, then how are they expressed?
Is this similar to how real solutions are expressed by parametric linear vector space by modulo 2? Or something else? I don't know. I am trying to google the answer for this question for days but I don't find the answer anywhere. It seems like nobody talks about this topic.
How?

New questions