Opened 8 years ago

Closed 2 years ago

# Normal cone of faces of polyhedra

Reported by: Owned by: darij major sage-9.1 geometry polytopes, linear programming, linear optimization, days100 gh-LaisRast, gh-kliem, chapoton, nailuj Jean-Philippe Labbé Jonathan Kliem N/A 7278f23 7278f23b2bd3178fd399d05d7fd171d808c9f834 #29155

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.

### comment:1 Changed 8 years ago by darij

• Description modified (diff)
• Summary changed from Normal vector to a polyhedron at a point... to Normal vector to a polyhedron at a face...

### comment:2 Changed 8 years ago by darij

• Description modified (diff)
• Summary changed from Normal vector to a polyhedron at a face... to Bounding lines for polyhedra

### comment:3 Changed 8 years ago by darij

• Description modified (diff)
• Summary changed from Bounding lines for polyhedra to Bounding hyperplanes for polyhedra

### comment:4 Changed 8 years ago by darij

• Description modified (diff)

### comment:5 Changed 8 years ago by 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
```

### comment:6 Changed 8 years ago by darij

Thanks, this makes it a lot easier.

### comment:7 Changed 5 years ago by moritz

• Status changed from new to needs_info

Should this remain open?

### comment:8 Changed 5 years ago by jipilab

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

### comment:9 Changed 3 years ago by 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).

### comment:10 Changed 3 years ago by jipilab

• Component changed from combinatorics to geometry
• Description modified (diff)
• Milestone changed from sage-6.4 to sage-8.9
• Status changed from needs_info to needs_work
• Summary changed from Bounding hyperplanes for polyhedra to Supporting cone & normal cone of faces of polyhedra

### comment:11 Changed 3 years ago by jipilab

• Authors set to Jean-Philippe Labbé
• Branch set to u/jipilab/17215
• Cc gh-LaisRast gh-kliem chapoton added
• Commit set to 302ec4609ea007b9c89001b91b1890961e535274
• Dependencies set to #27973

New commits:

 ​302ec46 `First version`

### comment:12 Changed 3 years ago by jipilab

• Summary changed from Supporting cone & normal cone of faces of polyhedra to Normal cone of faces of polyhedra
• Type changed from task to enhancement

### comment:13 follow-up: ↓ 14 Changed 3 years ago by 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.

### comment:14 in reply to: ↑ 13 Changed 3 years ago by jipilab

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

### comment:15 Changed 3 years ago by git

• Commit changed from 302ec4609ea007b9c89001b91b1890961e535274 to 2f8e3a95d9c4d2eac294ba40491427d7a81d7c16

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

 ​2f8e3a9 `Changed to use parent`

### comment:16 Changed 3 years ago by 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...

### comment:17 Changed 3 years ago by jipilab

• Branch changed from u/jipilab/17215 to u/jipilab/17215rebsed
• Commit changed from 2f8e3a95d9c4d2eac294ba40491427d7a81d7c16 to 12581fd5b643d482bd0ba66fbd32d845ca8df035
• Status changed from needs_work to needs_review

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`

### comment:18 Changed 3 years ago by gh-kliem

• Status changed from needs_review to needs_work

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

### comment:19 Changed 3 years ago by gh-kliem

• Dependencies changed from #27973 to #27973, #28646

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

### comment:20 Changed 2 years ago by embray

• Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

### comment:21 Changed 2 years ago by jipilab

• Branch changed from u/jipilab/17215rebsed to u/jipilab/17215reb2
• Commit changed from 12581fd5b643d482bd0ba66fbd32d845ca8df035 to 2f114d8e76529192f5879b75c5a368f0b1acc010
• Status changed from needs_work to needs_review

New commits:

 ​2f114d8 `First version`

### comment:22 Changed 2 years ago by jipilab

Rebased due to conflict. Needs review.

### comment:23 Changed 2 years ago by gh-LaisRast

• Status changed from needs_review to needs_work

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

### comment:24 Changed 2 years ago by git

• Commit changed from 2f114d8e76529192f5879b75c5a368f0b1acc010 to 4b803a144fc01e1a4336421b0343dbeec310c789

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

 ​4b803a1 `moved back the method`

### comment:25 Changed 2 years ago by jipilab

• Status changed from needs_work to needs_review

### comment:26 follow-up: ↓ 29 Changed 2 years ago by gh-LaisRast

• Status changed from needs_review to needs_work

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.

### comment:27 Changed 2 years ago by git

• Commit changed from 4b803a144fc01e1a4336421b0343dbeec310c789 to 31906994cfeaa60abca4df9970edea2ce183ae8a

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

 ​3190699 `fixed construction normal cone`

### comment:28 Changed 2 years ago by jipilab

• Status changed from needs_work to needs_review

### comment:29 in reply to: ↑ 26 Changed 2 years ago by jipilab

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

### comment:30 follow-up: ↓ 31 Changed 2 years ago by gh-kliem

• Dependencies changed from #27973, #28646 to #29155

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

### comment:31 in reply to: ↑ 30 Changed 2 years ago by jipilab

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.

### comment:32 Changed 2 years ago by git

• Commit changed from 31906994cfeaa60abca4df9970edea2ce183ae8a to 060d2b38b49d99a787c2468c58a757f8656d6bc1

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`

### comment:33 Changed 2 years ago by gh-kliem

• Reviewers set to Jonathan Kliem
• Status changed from needs_review to needs_work

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.

### comment:34 Changed 2 years ago by git

• Commit changed from 060d2b38b49d99a787c2468c58a757f8656d6bc1 to 77d87d5ff776dad45d805318090e380d483cfb4c

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

 ​77d87d5 `fixed origin def`

### comment:35 Changed 2 years ago by jipilab

• Status changed from needs_work to needs_review

### comment:36 Changed 2 years ago by git

• Commit changed from 77d87d5ff776dad45d805318090e380d483cfb4c to 7278f23b2bd3178fd399d05d7fd171d808c9f834

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

 ​7278f23 `fixed doctest`

### comment:37 Changed 2 years ago by jipilab

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

### comment:38 Changed 2 years ago by gh-kliem

• Status changed from needs_review to positive_review

LGTM. Note that #28880 fixes the pyflakes warning.

### comment:39 Changed 2 years ago by vbraun

• Branch changed from u/jipilab/17215reb2 to 7278f23b2bd3178fd399d05d7fd171d808c9f834
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.