Normal cone of faces of polyhedra

[darijgr]

A point v on a convex polyhedron P is a vertex of P if and only if there exists an affine hyperplane in the linear span of P which intersects P only in v. Knowing such affine hyperplane is a good certificate for v being a vertex.

This ticket implements the method normal_cone for faces of polyhedra, consisting of all the directions of the normals to supporting hyperplanes of the specified face.

Depends on #29155

CC: @LaisRast @kliem @fchapoton @sagetrac-nailuj

Component: geometry

Keywords: polytopes, days100

Author: Jean-Philippe Labbé

Branch/Commit: 7278f23

Reviewer: Jonathan Kliem

Issue created by migration from https://trac.sagemath.org/ticket/17215

[darijgr]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-... assuming that the point is a vertex or a point on a bounding line/ray. Is there a simple way to get it in Sage? Otherwise, this should be added.
+... lying in the subspace that contains the polyhedron. Is there a simple way to get it in Sage? Otherwise, this should be added.

[darijgr]

Description changed:

--- 
+++ 
@@ -1 +1,3 @@
-... lying in the subspace that contains the polyhedron. Is there a simple way to get it in Sage? Otherwise, this should be added.
+As far as I recall, a point v on a convex polyhedron P is a vertex of P if and only if there exists a vector w in the linear span of P such that no real number p satisfies v + pw \in P. Knowing such a w is a good certificate for v being a vertex.
+
+Do we have a method for finding such a w ?

[darijgr]

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
-As far as I recall, a point v on a convex polyhedron P is a vertex of P if and only if there exists a vector w in the linear span of P such that no real number p satisfies v + pw \in P. Knowing such a w is a good certificate for v being a vertex.
+As far as I recall, a point v on a convex polyhedron P is a vertex of P if and only if there exists an affine hyperplane in the linear span of P which intersects P only in v. Knowing such a w is a good certificate for v being a vertex.
 
 Do we have a method for finding such a w ?

[darijgr]

Description changed:

--- 
+++ 
@@ -1,3 +1,5 @@
 As far as I recall, a point v on a convex polyhedron P is a vertex of P if and only if there exists an affine hyperplane in the linear span of P which intersects P only in v. Knowing such a w is a good certificate for v being a vertex.
 
 Do we have a method for finding such a w ?
+
+I assume similar things exist for higher-dimensional faces of P rather than vertices?

[vbraun]

comment:5

All backends right now compute both H/V-representation; the dual is of course a much more complete certificate that a vertex is really a vertex. Also, the bounding hyperplane is not canonical---which one to pick? If you really need one you can construct one from the incident hyperplane equations of the vertex (or, more generally, d-dimensional face).

sage: P = polytopes.n_cube(3)
sage: v = P.vertices()[0]
sage: v
A vertex at (-1, -1, -1)
sage: A = sum(h.A() for h in v.incident())
sage: b = sum(h.b() for h in v.incident())
sage: b, A
(3, (1, 1, 1))
sage: Polyhedron(eqns=[[b] + list(A)]) & P
A 0-dimensional polyhedron in QQ^3 defined as the convex hull of 1 vertex

[darijgr]

comment:6

Thanks, this makes it a lot easier.

[mo271]

comment:7

Should this remain open?