Normal cone of faces of polyhedra

[darij]

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.

[vbraun]

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

[darij]

Thanks, this makes it a lot easier.

[moritz]

Should this remain open?

[jipilab]

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

[gh-kliem]

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).

[jipilab]

New commits:

​302ec46

First version

[gh-kliem]

If you construct the polyhedron with via the_poly.parent() similar to e.g. many examples in #27926 you can avoid the import of the constructor.

Don't know if that's better.

[jipilab]

Replying to gh-kliem:

If you construct the polyhedron with via the_poly.parent() similar to e.g. many examples in #27926 you can avoid the import of the constructor.

Don't know if that's better.

Yes, might be cleaner yes...

[git]

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

​2f8e3a9

Changed to use parent

[jipilab]

Now, only waiting for the wedge to get merged. After that, I would change some constructions to make use of this new function to deduplicate some code...

[jipilab]

I decided to leave the wedge and face truncation construction as they are since they do not need an explicit polyhedron.

---

New commits:

​02f1417	First version
​aa8d87e	Changed to use parent
​477f73f	fixed tests
​12581fd	reverted changes on truncations

[gh-kliem]

You did not consider the case, where the polyhedron has equations.

In this case your considering one of two possible rays. Probably should only append rays for inequalities, but I'm not sure.

One question: How do we construct the hyperplane that interesects exactly the face from this (see description of ticket).

[gh-kliem]

#28646 changes the order of faces, which affects a doctest in this ticket.

[embray]

Ticket retargeted after milestone closed

[jipilab]

New commits:

​2f114d8

First version

[jipilab]

Rebased due to conflict. Needs review.

[gh-LaisRast]

You put the method under the function combinatorial_face_to_polyhedral_face. You need to change its location. Otherwise it is not accessible.

[git]

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

​4b803a1

moved back the method

[gh-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.

[git]

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

​3190699

fixed construction normal cone

[jipilab]

Replying to gh-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...

[gh-kliem]

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.

[jipilab]

Replying to gh-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.

[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

[gh-kliem]

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.

[git]

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

​77d87d5

fixed origin def

[git]

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

​7278f23

fixed doctest

[jipilab]

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

[gh-kliem]

LGTM. Note that #28880 fixes the pyflakes warning.