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

[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?

[jplab]

comment:8

Not sure... perhaps there could be a method in the class for polyhedron_faces giving the corresponding normal cone?

[kliem]

comment:9

To my understanding such a method for each face of a Polyhedron would also help #27973, such that one could construct a wedge over a face (not just a facet).

[jplab]

Changed keywords from polytopes to polytopes, days100

[jplab]

Author: Jean-Philippe Labbé

[jplab]

Dependencies: #27973

[jplab]

Commit: 302ec46

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3190699

fixed construction normal cone

[sagetrac-git]

Changed commit from 4b803a1 to 3190699

[jplab]

comment:29

Replying to @LaisRast:

I changed it to "needs_work" because it still does not work for non-full-dimensional polytopes.

On a (very) related topic, the method normal_fan of Polyhedron returns

ValueError: the normal fan is only defined for full-dimensional polytopes

for non-full-dimensional polytopes. It should return "not implemented" since normal_fan is defined for non-full-dimensional polytopes.

This should be addressed in a different ticket...

[kliem]

Changed dependencies from #27973, #28646 to #29155

[kliem]

comment:30

Reading carefully your doctests, one sees a bug, which will be fixed in #29155.

Instead of using faces for iteration you can use the new method face_generator.

[jplab]

comment:31

Replying to @kliem:

Reading carefully your doctests, one sees a bug, which will be fixed in #29155.

Aa ha!! I see I was also somehow confused by that, but did not think more about it.

Instead of using faces for iteration you can use the new method face_generator.

Good suggestion.

[sagetrac-git]

Changed commit from 3190699 to 060d2b3

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7c35b0e	face to face_generator
d7f47ad	initialize full-dimensional face with equations
e55569a	Merge branch 'public/29155' of trac.sagemath.org:sage into 17215
060d2b3	fixed doctest

[kliem]

Reviewer: Jonathan Kliem

[kliem]

comment:33

I think the following is more direct:

-        origin = parent.zero().vertices()[0].vector()
+        origin = self.ambient_space().zero()

Otherwise you can put it positive review on my behalf. Maybe wait for bots yet.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

77d87d5

fixed origin def

[sagetrac-git]

Changed commit from 060d2b3 to 77d87d5

[sagetrac-git]

Changed commit from 77d87d5 to 7278f23

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7278f23

fixed doctest

[jplab]

comment:37

There was an error... ambient_space doesn't exist for faces... So I fixed it.

[kliem]

comment:38

LGTM. Note that #28880 fixes the pyflakes warning.

[vbraun]

Changed branch from u/jipilab/17215reb2 to 7278f23