Opened 8 years ago
Closed 2 years ago
#17215 closed enhancement (fixed)
Normal cone of faces of polyhedra
Reported by:  darij  Owned by:  

Priority:  major  Milestone:  sage9.1 
Component:  geometry  Keywords:  polytopes, linear programming, linear optimization, days100 
Cc:  ghLaisRast, ghkliem, chapoton, nailuj  Merged in:  
Authors:  JeanPhilippe Labbé  Reviewers:  Jonathan Kliem 
Report Upstream:  N/A  Work issues:  
Branch:  7278f23 (Commits, GitHub, GitLab)  Commit:  7278f23b2bd3178fd399d05d7fd171d808c9f834 
Dependencies:  #29155  Stopgaps: 
Description (last modified by )
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.
Change History (39)
comment:1 Changed 8 years ago by
 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
 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
 Description modified (diff)
 Summary changed from Bounding lines for polyhedra to Bounding hyperplanes for polyhedra
comment:4 Changed 8 years ago by
 Description modified (diff)
comment:5 Changed 8 years ago by
comment:6 Changed 8 years ago by
Thanks, this makes it a lot easier.
comment:8 Changed 5 years ago by
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
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
 Component changed from combinatorics to geometry
 Description modified (diff)
 Keywords days100 added
 Milestone changed from sage6.4 to sage8.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
 Branch set to u/jipilab/17215
 Cc ghLaisRast ghkliem chapoton added
 Commit set to 302ec4609ea007b9c89001b91b1890961e535274
 Dependencies set to #27973
New commits:
302ec46  First version

comment:12 Changed 3 years ago by
 Cc nailuj added
 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 followup: ↓ 14 Changed 3 years ago by
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
comment:15 Changed 3 years ago by
 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
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
 Branch changed from u/jipilab/17215 to u/jipilab/17215rebsed
 Commit changed from 2f8e3a95d9c4d2eac294ba40491427d7a81d7c16 to 12581fd5b643d482bd0ba66fbd32d845ca8df035
 Status changed from needs_work to needs_review
comment:18 Changed 3 years ago by
 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
 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
 Milestone changed from sage8.9 to sage9.1
Ticket retargeted after milestone closed
comment:21 Changed 2 years ago by
 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
Rebased due to conflict. Needs review.
comment:23 Changed 2 years ago by
 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
 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
 Status changed from needs_work to needs_review
comment:26 followup: ↓ 29 Changed 2 years ago by
 Status changed from needs_review to needs_work
I changed it to "needs_work" because it still does not work for nonfulldimensional polytopes.
On a (very) related topic, the method normal_fan
of Polyhedron returns
ValueError: the normal fan is only defined for fulldimensional polytopes
for nonfulldimensional polytopes. It should return "not implemented" since normal_fan
is defined for nonfulldimensional polytopes.
comment:27 Changed 2 years ago by
 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
 Status changed from needs_work to needs_review
comment:29 in reply to: ↑ 26 Changed 2 years ago by
Replying to ghLaisRast:
I changed it to "needs_work" because it still does not work for nonfulldimensional polytopes.
On a (very) related topic, the method
normal_fan
of Polyhedron returnsValueError: the normal fan is only defined for fulldimensional polytopesfor nonfulldimensional polytopes. It should return "not implemented" since
normal_fan
is defined for nonfulldimensional polytopes.
This should be addressed in a different ticket...
comment:30 followup: ↓ 31 Changed 2 years ago by
 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
comment:32 Changed 2 years ago by
 Commit changed from 31906994cfeaa60abca4df9970edea2ce183ae8a to 060d2b38b49d99a787c2468c58a757f8656d6bc1
comment:33 Changed 2 years ago by
 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
 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
 Status changed from needs_work to needs_review
comment:36 Changed 2 years ago by
 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
There was an error... ambient_space
doesn't exist for faces... So I fixed it.
comment:38 Changed 2 years ago by
 Status changed from needs_review to positive_review
LGTM. Note that #28880 fixes the pyflakes warning.
comment:39 Changed 2 years ago by
 Branch changed from u/jipilab/17215reb2 to 7278f23b2bd3178fd399d05d7fd171d808c9f834
 Resolution set to fixed
 Status changed from positive_review to closed
All backends right now compute both H/Vrepresentation; the dual is of course a much more complete certificate that a vertex is really a vertex. Also, the bounding hyperplane is not canonicalwhich one to pick? If you really need one you can construct one from the incident hyperplane equations of the vertex (or, more generally, ddimensional face).