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: | sage-9.1 |
Component: | geometry | Keywords: | polytopes, linear programming, linear optimization, days100 |
Cc: | gh-LaisRast, gh-kliem, chapoton, nailuj | Merged in: | |
Authors: | Jean-Philippe 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 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
- 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
- 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 follow-up: ↓ 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 sage-8.9 to sage-9.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 follow-up: ↓ 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 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
- 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 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 returnsValueError: the normal fan is only defined for full-dimensional polytopesfor 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
- 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/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).