<p>(I'm going to use the word “polyhedron” instead of “polytope” because I haven't considered how to generalize it to more dimensions.)</p>
<ol>
<li><p>Being constructed of the intersection of half-spaces, the polyhedron must be convex; the interior volume is a region containing none of the planes.</p>
</li>
<li><p>We can classify the intersection points of 3 unequal planes as follows:</p>
<ul>
<li>There cannot be an intersection point within the polyhedron, because per (1), none of the planes intersect the polyhedron.</li>
<li>If it is on the surface, then it must be a vertex; it cannot lie on an edge or face because if it did, that would contradict the 3 planes defining a point.</li>
<li>If it is outside the polyhedron, then it must not be a vertex.</li>
</ul>
</li>
<li><p>If an intersection point lies within the outside half of <em>any one</em> of the half-spaces making up the polyhedron, then it cannot be inside or on the surface of the polyhedron per (1), and therefore cannot be a vertex per (2).</p>
</li>
<li><p>If an intersection point <em>does not</em> lie within the outside half of any half-space, then it cannot be inside per (1), so it must be on the surface of the polyhedron, and therefore per (2) must be a vertex.</p>
</li>
</ol>
<p>Therefore, it suffices to discard all intersections which are outside <em>any one</em> of the half-spaces.</p>
<p>This can be seen as applying the <em>separating axis theorem</em> to the points; every plane defines a potential separating axis.</p>

CC BY-SA 4.0
2023-08-13T14:59:03.523Z
2023-08-13T14:59:03.523Z
Kevin Reid
<p>Assume that in 3D we have a polytope defined by the intersection of halfspaces.</p>
<p>A half space is the set of all solutions of a linear inequality <span class="math-container">$P = N \cdot x + c \leq 0$</span> Where <span class="math-container">$N$</span> is the normal to the half space.</p>
<p>The polytope is thus the boundary of <span class="math-container">$\cap_{i=0} P_i$</span> <span class="math-container">$P_i = N_i \cdot x + c_i \leq 0$</span>.</p>
<p>In 3D all vertices must be intersections of at least 3 planes. i.e. all vertices are a subset of all points such that:</p>
<p><span class="math-container">$$P_i = P_j = P_k = 0$$</span></p>
<p>Which is a trivial 3x3 system that can be easily solved.</p>
<p>However, the total number of points that you get out of this is exponentially larger than the actual number of points on the polytope.</p>
<p>For example in this diagram:</p>
<p><a href="https://i.sstatic.net/c48wo.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/c48wo.png" alt="enter image description here" /></a></p>
<p>The top plane intersects the other 2 at points which are not vertices of the polytope.</p>

CC BY-SA 4.0
2023-08-13T02:29:04.640Z
I am not sure what the figure means here. My understanding is that in this figure, the normals of these planes form linear relationship. Since normal is orthogonal to any given line on that plane, so we know the intersection of two planes defines a line of which the direction can be calculated by the cross product of two normals. Since all three normals are on the same plane (due to linear relationship), the intersection lines will be parallel to each other, so the system has no solution thus no vertex. When these lines are exactly the same, then you will have infinite number of solutions.
Enigmatisms
CC BY-SA 4.0
2023-08-13T02:38:15.290Z
So If I understand correctly, you can check the determinant of the 3x3 system before solving for the vertex. If the determinant is 0 (or its absolute value is extremely small), there won't be a good solution for you.
Enigmatisms
CC BY-SA 4.0
2023-08-13T04:55:11.977Z
@Enigmatisms I perhaps was unclear, you have arbitrarily many of these planes, not just 3 and you are looking for the vertices of the underlying polytope.
Makogan
<mathematics><computational-geometry><linear-algebra>
Finding vertices of a polytope?
Makogan
# Finding vertices of a polytope?

(Asked by: username_0 on 2023-08-12)

Assume that in 3D we have a polytope defined by the intersection of halfspaces.

A half space is the set of all solutions of a linear inequality $P = N \cdot x + c \leq 0$ Where $N$ is the normal to the half space.

The polytope is thus the boundary of $\cap\_{i=0} P\_i$ $P\_i = N\_i \cdot x + c\_i \leq 0$.

In 3D all vertices must be intersections of at least 3 planes. i.e. all vertices are a subset of all points such that:

$$P\_i = P\_j = P\_k = 0$$

Which is a trivial 3x3 system that can be easily solved.

However, the total number of points that you get out of this is exponentially larger than the actual number of points on the polytope.

For example in this diagram:

[![enter image description here](https://i.sstatic.net/c48wo.png)](https://i.sstatic.net/c48wo.png)

The top plane intersects the other 2 at points which are not vertices of the polytope.

**Tags:** mathematics, computational-geometry, linear-algebra

> **Comments:**
> **username_1**: I am not sure what the figure means here. My understanding is that in this figure, the normals of these planes form linear relationship. Since normal is orthogonal to any given line on that plane, so we know the intersection of two planes defines a line of which the direction can be calculated by the cross product of two normals. Since all three normals are on the same plane (due to linear relationship), the intersection lines will be parallel to each other, so the system has no solution thus no vertex. When these lines are exactly the same, then you will have infinite number of solutions.  
> **username_1**: So If I understand correctly, you can check the determinant of the 3x3 system before solving for the vertex. If the determinant is 0 (or its absolute value is extremely small), there won't be a good solution for you.  
> **username_0**: @username_1 I perhaps was unclear, you have arbitrarily many of these planes, not just 3 and you are looking for the vertices of the underlying polytope.  

---

## 1 answers

### Answer by username_2 on 2023-08-13. Score: 1

(I'm going to use the word “polyhedron” instead of “polytope” because I haven't considered how to generalize it to more dimensions.)

1. Being constructed of the intersection of half-spaces, the polyhedron must be convex; the interior volume is a region containing none of the planes.
2. We can classify the intersection points of 3 unequal planes as follows:

   * There cannot be an intersection point within the polyhedron, because per (1), none of the planes intersect the polyhedron.
   * If it is on the surface, then it must be a vertex; it cannot lie on an edge or face because if it did, that would contradict the 3 planes defining a point.
   * If it is outside the polyhedron, then it must not be a vertex.
3. If an intersection point lies within the outside half of *any one* of the half-spaces making up the polyhedron, then it cannot be inside or on the surface of the polyhedron per (1), and therefore cannot be a vertex per (2).
4. If an intersection point *does not* lie within the outside half of any half-space, then it cannot be inside per (1), so it must be on the surface of the polyhedron, and therefore per (2) must be a vertex.

Therefore, it suffices to discard all intersections which are outside *any one* of the half-spaces.

This can be seen as applying the *separating axis theorem* to the points; every plane defines a potential separating axis.


---

