# compute the intersection of two polytopes and it's corner points

I am looking for a method in python/matlab to calculate the corner points of polytope which is an intersection of a polytope with half spaces.

I have a polytope P1 of the form

• -1<= x0 <= 1
• -1<= x1 <= 1
• -1<= x2 <= 1
• -1<= x3 <= 1

And half spaces defined by the equations as in the following format.

• -0.1 * x0 + 1.0 * x1 + 2.0 * x2 + 0.8 * x3 + 6.5 > 0
• 1.5 * x0 + 0.5 * x1 + -3.5 * x2 + 0.4 * x3 + 6.0 > 0
• 1.2 * x0 + 1.8 * x1 + 15.0 * x2 + 2.5 * x3 + 1.0 > 0
• -1.5 * x0 + -0.5 * x1 + 3.0 * x2 + 1.5 * x3 + 6.2 > 0

I wanted to compute a polytope P2 as the intersection of the polytope P1 with half spaces defined by the equations similar to the equations mentioned above. Then I need to compute the corner points of the intersected polytope P2.

I used python script.linprog for the computing the intersection of polytopes by using the vertical stacking method. But don't know how to calculate the corner points.

• Coding questions (how do i implement this in Python/Matlab?) are generally off-topic here. Asking for algorithms is fine. See our help center.
– D.W.
Oct 12, 2023 at 17:12

An example Pyton script using the scipy.optimize.linprog function.

from scipy.optimize import linprog

import numpy as np

# Define coefficients of the half-space inequalities
A = np.array([
[-0.1, 1.0, 2.0, 0.8],
[1.5, 0.5, -3.5, 0.4],
[1.2, 1.8, 15.0, 2.5],
[-1.5, -0.5, 3.0, 1.5]
])

# Define right-hand side of the inequalities
b = np.array([6.5, 6.0, 1.0, 6.2])

# Define bounds for the variables (P1)
x_bounds = [(0, 1) for _ in range(4)]

# Use linprog to find the corner points of intersection
result = linprog(c=np.zeros(4), A_ub=A, b_ub=b, bounds=x_bounds, method='highs')

# Extract corner points
corner_points = result.x

print("Corner Points of the Intersection:")
print(corner_points)


Hopefully it’s self explanitary with the comments. Just ask if you need anything explained and I’ll edit the answer.

Representing the polyhedron of feasible solutions as the intersection of half spaces, defined by linear inqualities, is known as H-representation.

Representing that polyhedron by a list of its vertices (and its rays) is known as V-representation.

So, your problem amounts to converting from H-representation to V-representation. A search on those terms will turn up many algorithms and software libraries that you can use for this purpose.

Be prepared that it can take exponential time, as there can be exponentially many vertices.