Suppose P is a polyhedron whose representation as a system of linear inequalities is given to

Ayanna Trujillo

Ayanna Trujillo

Answered question

2022-06-07

Suppose P is a polyhedron whose representation as a system of linear inequalities is given to us:
P = { x   |   A x b }
Define P be the image of P under the linear transformation which maps x to C x:
P = { C x   |   x P } .
Given A , b , C, our goal is to compute a representation of P as a system of linear inequalities, i.e., to compute D , e satisfying
P = { x   |   D x e } .
What is the complexity of this problem (i.e., how many arithmetic operations or bit operations are required)?

Answer & Explanation

plodno8n

plodno8n

Beginner2022-06-08Added 17 answers

You can switch from H-representation to V representation of P. Once you have the vertex v P of P you can find the vertex in the co-domain as v P 1 = C v P . Then you can use any convex hull algorithm using the points to find the image.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?