Find the intersection of two or more polygons in terms

Lucian Maddox 2022-07-15 Answered
Find the intersection of two or more polygons in terms of linear inequalities
Given two or more closed polygons each defined by a system of linear inequalities, is there any method by which their intersection polygon may be determined, also in terms of a system of linear inequalities?
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)

diamondogsaz
Answered 2022-07-16 Author has 12 answers
In general, the number of inequalities used to describe one convex polytope (high dimensional polygon) may not equal the number needed to describe another, even if they share the same dimension.
Consider a triangle, which in R 2 requires 3, while a pentagon requires 5.
If A is the set of linear inequalities for one polygon and B is the set of linear inequalities for another, you could consider A B to describe their intersection.
Did you like this example?
Subscribe for all access

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-07-10
{ y 2 3 0 16 y 4 96 y 2 0
the solution for the first inequality is y 3 or y 3 and the solution for the second inequality is 6 y 6 . Then for my result the solution for the system is
Then for my result the solution for the system is or 3 y 6
asked 2022-06-08
How to check if a system of linear inequalities is solvable or not?
I have the variables x 1 , x 2 , . . . , x n and the following relations:
x 1 ρ 1 x 2
x 2 ρ 2 x 3
...
x n 1 ρ n 1 x n ,
where the relations ρ i [ = , < , > ] are known. How to check if the system of inequalities above are consistent or not?
asked 2022-07-13
Consider the system
{ 1 = A + B = C + D B C
with A , B , C , D positive.
Does the system imply that A D?
asked 2022-06-20
Suppose I have an element-wise inequality: A x b, where A is a rectangular matrix with full row rank, and x and b are appropriately sized column vectors. I need to check if the inequality holds to branch some code I'm writing.
If I (thin) LQ decompose A, I have:
where L is a lower triangular square matrix of full rank and Q is an orthogonal matrix.
As it turns out, I need to calculate L 1 b anyway, so my first thought was to calculate it and just check:
Q x L 1 b
However, this doesn't necessarily work, as depending on exactly how the matrix A was decomposed, it might change the in to a . For example, if A = 1, and we decompose it as L = 1, Q = 1, multiplying both sides by L 1 switches the direction of the inequality.
Under what circumstances will multiplying both sides of an inquality system by a matrix not change the direction of the inequality? My intuitive guess is that as long as the eigenvalues of the matrix are positive (that is, the matrix is positive definite), the inequality direction won't change. But I'm not sure how to prove/disprove that.
asked 2022-05-27
Let P be a polyhedron in [ 0 , 1 ] n defined by the constraints A x b for A R m × n , x R n , and b R m .
In the solutions of an exercise, the following is mentioned:
"Since the first n constraints are linearly independent, they correspond to a basic solution of the system which, a priori, may be feasible or infeasible. This solution is obtained by replacing inequalities with equalities and computing the unique solution of this linear system."
So I am quite confused about this:
1) Why does "linear independent constraints" imply that "basic solution"?
2) Is a basic solution not always feasible?
asked 2021-02-11
describe the sets of points in space whose coordinates satisfy the given inequalities or combinations of equations and inequalities. x2+y2+z21
asked 2022-06-14
Prove that if the linear system A x = b is perturbed in both A and b
( A + δ A ) ( x + δ x ) = b + δ b
then
δ x x κ ( A ) 1 κ ( A ) δ A A ( δ A A + δ b b )