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 ?

Question

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  ?

Jaylee Dodson · Accepted Answer

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 · Accepted Answer

Just the vertices isn&#039;t enough to determine the polytope, unless you also know that it&#039;s convex. If it&#039;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.

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

Answered question

Answer & Explanation

New Questions in Algebra I