Let P 1 </msub> and P 2 </msub> being two polytopes defined

Llubanipo

Llubanipo

Answered question

2022-06-24

Let P 1 and P 2 being two polytopes defined by their vertices.
Is there any efficient way to compute P 3 = P 1 P 2 ?

Answer & Explanation

Jaylee Dodson

Jaylee Dodson

Beginner2022-06-25Added 22 answers

Considering that one defines a convex polytope as the convex hull of a finite number of vertices the so called H-representation in the comment section can also be a representation of the polytope by means of the following theorem:
Theorem: A non-empty set P of Rn is a (convex) polytope if, and only if, it is a bounded polyhedral set.
Since a bounded polyhedral is already defined as the intersection of halfspaces and the intersection of bounded sets is again bounded you might do just as it was stated in the comments:
P 1 P 2 = { x R n : A x b , A x b } ,
This problem does not characterizes itself as an LP but there are different problems that use the new polytope P that can be stated in the form of an LP. An example can be finding the smallest distance between a given point outside the polytope and the polytope.
gledanju0

gledanju0

Beginner2022-06-26Added 2 answers

Just the vertices isn't enough to determine the polytope, unless you also know that it's convex. If it's convex you should start by finding the convex hull, which will tell you the topology of the polytope: which vertices share edges, which cycles of edges form faces, etc.

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?