Opened 2 years ago
Closed 20 months ago
#27689 closed enhancement (fixed)
Implement is_pyramid, is_bipyramid, is_prism for polytopes
Reported by:  ghLaisRast  Owned by:  

Priority:  major  Milestone:  sage8.9 
Component:  geometry  Keywords:  polytopes, pyramid, bipyramid, prism, days100 
Cc:  jipilab, ghkliem  Merged in:  
Authors:  Laith Rastanawi, Jonathan Kliem  Reviewers:  JeanPhilippe Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  5764ce4 (Commits, GitHub, GitLab)  Commit:  5764ce4f3d48c6a9969211a94429c28a305b7345 
Dependencies:  Stopgaps: 
Description (last modified by )
Implement the following methods in geometry/polyhedron/base.py
:
is_pyramid
: test whether the polytope is a pyramid over one of its facetsis_bipyramid
: test whether the polytope is combinatorially equivalent to a bipyramid over some polytopeis_prism
: test whether the polytope is combinatorially equivalent to a prism of some polytope
Change History (55)
comment:1 Changed 2 years ago by
 Branch set to public/27689
 Commit set to 41b554bd54eab1775b0e0b479a8e9c8af326b2bf
 Status changed from new to needs_review
comment:2 followup: ↓ 7 Changed 2 years ago by
comment:3 followup: ↓ 4 Changed 2 years ago by
Actually, much easier.
The edges of the polytope, not contained in F_1 or F_2 provide such a matching (if the polytope is a prism).
Getting the edges is not fast at the moment, but it will be soon.
comment:4 in reply to: ↑ 3 Changed 2 years ago by
Replying to ghkliem:
Actually, much easier.
The edges of the polytope, not contained in F_1 or F_2 provide such a matching (if the polytope is a prism).
Getting the edges is not fast at the moment, but it will be soon.
So, just counting the number of those edges would do the job.
comment:5 Changed 2 years ago by
 Commit changed from 41b554bd54eab1775b0e0b479a8e9c8af326b2bf to 76caa3eca94e38207d84e2ff5f5d55ceb70bbc08
Branch pushed to git repo; I updated commit sha1. New commits:
76caa3e  typos and change the certificate of is_pyramid

comment:6 followup: ↓ 8 Changed 2 years ago by
 Commit changed from 76caa3eca94e38207d84e2ff5f5d55ceb70bbc08 to b67c9ae531d44d8e5d52348f6a3aa5b83788898e
Branch pushed to git repo; I updated commit sha1. New commits:
b67c9ae  remove x = None in change_ring so that pyflakes stops showing error

comment:7 in reply to: ↑ 2 Changed 2 years ago by
 Status changed from needs_review to needs_work
I changed the certificate of is_pyramid
and fixed the typos.
I changed the status of the ticket to "needs work" until either I give an argument why the code for is_bipyramid
and is_prism
works (if it works) or implement another way.
Replying to ghkliem:
Somehow all those methods should move to
CombinatorialPolyhedron
(#26887) eventually. However, this might take some time until it actually happens.weather > whether
is_pyramid
 I find the apex of the pyramid to be a more natural certificate (would also be consistend with
is_bipyramid
##
>#
Polyhedron(vertices=[[]]).is_pyramid
will yieldFalse
, asincidence_matrix
is not what one would expect in this case Delete empty line at the end of the docstring
We should do changes in
pyramid
as well:
pyramid
should not be defined for unbounded polyhedra, this will not yield the convex hull (the convex hull is not even closed)
 Also
Polyhedron().pyramid()
does not work, but should yield the 0dimensional polytope delete empty line at end of docstring
tow
>two
At the moment I'm not sure whether the code for bipyramide and prism is correct. I have to think about it. There might be some weird counterexample in high dimensions.
I think one should do prism in the following way:
A polytope is a prism if we find facets F_1,F_2 with vertices x_1,...,x_n resp. y_1,...,y_n such that they are exactly all vertices (so far so good).
Also they can be labeled (as I indicated) such that for each other facet either x_i and y_i are contained in it or neither.
To find this labeling is a nontrivial combinatorial task, I would say.
Basically we want to know whether a bipartite graph has a perfect matching.
For the bipyramid we do the dual approach.
comment:8 in reply to: ↑ 6 Changed 2 years ago by
In the ticket #27534 I added x = None
in the method change_ring
so that pyflakes stops showing an error for undefined variable. However, at some point, someone changed the original code for change_ring
in #22574 making x
unneeded.
So I removed the line x = None
now so that pyflakes stops showing an error for unneeded variable.
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
b67c9ae remove x = None in change_ring so that pyflakes stops showing error
comment:9 Changed 2 years ago by
 Commit changed from b67c9ae531d44d8e5d52348f6a3aa5b83788898e to 9db57df9790d6936da398d09744c57e5347650a6
Branch pushed to git repo; I updated commit sha1. New commits:
9db57df  delete empty lines

comment:10 Changed 2 years ago by
What about using the gale transform to know about these things? I believe this would be very fast.
See Section 5.4 in "Convex polytopes" of Grünbaum.
comment:11 followup: ↓ 12 Changed 2 years ago by
The gale transform is pretty slow, I believe. Completing something to an orthonormal basis involves hard computations as far as I know (33s for the 5dimensional permutahedron on my machine, 5s for the 9dimensional cube).
This is what one should do for the bipyramid:
 Let
a
,b
the candidates for the apexes of a polytopeP
.  P is a bipyramid over
a
andb
, if and only if the vertex figures are identical.
Hence we can take all facets incident to a
in their vertexrepresentation and delete a
from them. E.g. (v_1,v_2,v_3,a) > (v_1,v_2,v_3).
Likewise we proceed for b
.
If the two lists (of ridges of P
) are identical, then this is a bipyramid over a
and b
, otherwise not.
This check should be arithmetically very fast (especially since there shouldn't be many candidates for a
and b
).
Does what I'm saying make any sense? Is this correct?
Likewise one could proceed with the prism, just with facetincidences of vertices/edges.
comment:12 in reply to: ↑ 11 ; followup: ↓ 13 Changed 2 years ago by
Replying to ghkliem:
The gale transform is pretty slow, I believe. Completing something to an orthonormal basis involves hard computations as far as I know (33s for the 5dimensional permutahedron on my machine, 5s for the 9dimensional cube).
All the Gale transform needs to do is to compute a basis for the kernel of the vertices matrix. This does not have high complexity. Then, to check if the polytope is pyramidal at a vertex x
, one just checks if the corresponding dual vertex is the 0
vector. (See Theorem 3 from p.88 in Grünbaum) You do not need to do orthonormal basis computations for that.
This is what one should do for the bipyramid:
 Let
a
,b
the candidates for the apexes of a polytopeP
. P is a bipyramid over
a
andb
, if and only if the vertex figures are identical.
This is False
. Take a prism over a polygon, then stack the two polygons. The stacked vertices have identical vertex figures, but the polytope is obviously not a bipyramid.
Further, computing vertex figures are costly if not done properly. (Imagine creating one Polyhedron object for each vertex and then, what? Check isomorphism types?
Getting the kernel as above is not too hard, and uses significantly less memory than creating tons of objects for each vertex in the input.
Hence we can take all facets incident to
a
in their vertexrepresentation and deletea
from them. E.g. (v_1,v_2,v_3,a) > (v_1,v_2,v_3). Likewise we proceed forb
. If the two lists (of ridges ofP
) are identical, then this is a bipyramid overa
andb
, otherwise not.This check should be arithmetically very fast (especially since there shouldn't be many candidates for
a
andb
).Does what I'm saying make any sense? Is this correct?
Likewise one could proceed with the prism, just with facetincidences of vertices/edges.
> I don't understand what this is doing.
comment:13 in reply to: ↑ 12 ; followup: ↓ 14 Changed 2 years ago by
Replying to jipilab:
Replying to ghkliem:
The gale transform is pretty slow, I believe. Completing something to an orthonormal basis involves hard computations as far as I know (33s for the 5dimensional permutahedron on my machine, 5s for the 9dimensional cube).
All the Gale transform needs to do is to compute a basis for the kernel of the vertices matrix. This does not have high complexity. Then, to check if the polytope is pyramidal at a vertex
x
, one just checks if the corresponding dual vertex is the0
vector. (See Theorem 3 from p.88 in Grünbaum) You do not need to do orthonormal basis computations for that.
How do you do bipyramid? 'is_pyramid' is already in a state we are pretty happy with?
I never really looked into it, I just noticed that it does a significant amount of time.
This is what one should do for the bipyramid:
 Let
a
,b
the candidates for the apexes of a polytopeP
. P is a bipyramid over
a
andb
, if and only if the vertex figures are identical.This is
False
. Take a prism over a polygon, then stack the two polygons. The stacked vertices have identical vertex figures, but the polytope is obviously not a bipyramid.
There was a reason I said identical and not isomorphic. I should have said combinatorially identical (take all faces containing 'a' and delete 'a', this way one obtains the vertex figure of 'a', actually the facets suffice for checking).
Further, computing vertex figures are costly if not done properly. (Imagine creating one Polyhedron object for each vertex and then, what? Check isomorphism types?
We just need the facets as vertexincidences. This is incredible cheap. Also there is no need to determine the combinatorial type, as we really check for equality.
Getting the kernel as above is not too hard, and uses significantly less memory than creating tons of objects for each vertex in the input.
Hence we can take all facets incident to
a
in their vertexrepresentation and deletea
from them. E.g. (v_1,v_2,v_3,a) > (v_1,v_2,v_3). Likewise we proceed forb
. If the two lists (of ridges ofP
) are identical, then this is a bipyramid overa
andb
, otherwise not.This check should be arithmetically very fast (especially since there shouldn't be many candidates for
a
andb
).Does what I'm saying make any sense? Is this correct?
Likewise one could proceed with the prism, just with facetincidences of vertices/edges.
> I don't understand what this is doing.
comment:14 in reply to: ↑ 13 ; followup: ↓ 15 Changed 2 years ago by
Replying to ghkliem:
Replying to jipilab:
Replying to ghkliem:
The gale transform is pretty slow, I believe. Completing something to an orthonormal basis involves hard computations as far as I know (33s for the 5dimensional permutahedron on my machine, 5s for the 9dimensional cube).
All the Gale transform needs to do is to compute a basis for the kernel of the vertices matrix. This does not have high complexity. Then, to check if the polytope is pyramidal at a vertex
x
, one just checks if the corresponding dual vertex is the0
vector. (See Theorem 3 from p.88 in Grünbaum) You do not need to do orthonormal basis computations for that.How do you do bipyramid? 'is_pyramid' is already in a state we are pretty happy with?
 Bipyramid can also be checked via gale duality.
 I agree that there is the green light from the bot. Nevertheless, if the ticket is not merged yet and we can think about a better implementation that could be faster, we should try it.
There was a reason I said identical and not isomorphic. I should have said combinatorially identical (take all faces containing 'a' and delete 'a', this way one obtains the vertex figure of 'a', actually the facets suffice for checking).
Still does not make your procedure work as far as I understand it.
We just need the facets as vertexincidences. This is incredible cheap. Also there is no need to determine the combinatorial type, as we really check for equality.
Being a bipyramid involves more than combinatorics of adjacencies. Think about two centrallysymmetric vertices of the cube, everything you may come up with will give the same on both of them, nevertheless, the cube remains not a bipyramid. Cocircuits encodes bipyramid very conveniently and Gale transform gives you access to them. This is why I mentioned that it would be worth looking into it.
comment:15 in reply to: ↑ 14 Changed 2 years ago by
Replying to jipilab:
Replying to ghkliem:
Replying to jipilab:
Replying to ghkliem:
The gale transform is pretty slow, I believe. Completing something to an orthonormal basis involves hard computations as far as I know (33s for the 5dimensional permutahedron on my machine, 5s for the 9dimensional cube).
All the Gale transform needs to do is to compute a basis for the kernel of the vertices matrix. This does not have high complexity. Then, to check if the polytope is pyramidal at a vertex
x
, one just checks if the corresponding dual vertex is the0
vector. (See Theorem 3 from p.88 in Grünbaum) You do not need to do orthonormal basis computations for that.How do you do bipyramid? 'is_pyramid' is already in a state we are pretty happy with?
 Bipyramid can also be checked via gale duality.
As long as it gets more information than vertexfacet incidences…
 I agree that there is the green light from the bot. Nevertheless, if the ticket is not merged yet and we can think about a better implementation that could be faster, we should try it.
'is_pyramid' should be almost as fast as it gets. If there is a vertex adjacent to all but one facet, it's a pyramid. Doing Gale transform is much slower, as we already have vertexfacetincidences cached.
There was a reason I said identical and not isomorphic. I should have said combinatorially identical (take all faces containing 'a' and delete 'a', this way one obtains the vertex figure of 'a', actually the facets suffice for checking).
Still does not make your procedure work as far as I understand it.
We just need the facets as vertexincidences. This is incredible cheap. Also there is no need to determine the combinatorial type, as we really check for equality.
Being a bipyramid involves more than combinatorics of adjacencies. Think about two centrallysymmetric vertices of the cube, everything you may come up with will give the same on both of them, nevertheless, the cube remains not a bipyramid. Cocircuits encodes bipyramid very conveniently and Gale transform gives you access to them. This is why I mentioned that it would be worth looking into it.
This is not a counterexample to my approach. The vertex figures are just not identical. They are isomorphic, but not identical. One might have to require that each facet is adjacent to 'a' or 'b'.
This approach proves that the polytope is combinatorially equivalent to the bipyramid over the vertex figure of 'a'. Then it is a bipyramid. This is as much detail as I'm willing to provide now. I can give more detail on Monday.
comment:16 Changed 22 months ago by
 Milestone changed from sage8.8 to sage8.9
Tickets still needing working or clarification should be moved to the next release milestone at the soonest (please feel free to revert if you think the ticket is close to being resolved).
comment:17 Changed 22 months ago by
Gale transform (or its implementation) is much slower than incidence matrix at the moment.
I'm thinking about starting my own branch on top of this one and implementing is_bipyramid
and is_prism
along with a proof in one docstring. Any thoughts?
comment:18 Changed 22 months ago by
 Description modified (diff)
comment:19 Changed 22 months ago by
 Branch changed from public/27689 to public/27689bis
 Commit changed from 9db57df9790d6936da398d09744c57e5347650a6 to 513d852550386bd498056c17a6ce37134915e029
 Status changed from needs_work to needs_review
comment:20 Changed 21 months ago by
 Keywords days100 added
 Status changed from needs_review to needs_work
resolving conflicts
comment:21 Changed 21 months ago by
 Commit changed from 513d852550386bd498056c17a6ce37134915e029 to f22fc0e032d78d46a369cd1c1712ccd0dd21532e
Branch pushed to git repo; I updated commit sha1. New commits:
f22fc0e  Merge branch 'public/27689bis' of git://trac.sagemath.org/sage into is_bipyramid

comment:22 Changed 21 months ago by
 Status changed from needs_work to needs_review
comment:23 followup: ↓ 24 Changed 21 months ago by
 Status changed from needs_review to needs_work
Here are a few suggestions to fix:
def is_pyramid(self, certificate=False): """ Test whether the polytope is a pyramid over one of its facets. INPUT: +  ``certificate``  boolean (default: ``False``); specifies whether + to return a vertex of the polytope which is the apex of a pyramid, + if found.   ``certificate``  (default: ``False``) boolean; specifies whether  to return a vertex of the polytope which is the apex of a pyramid,  if found
In the OUTPUT
, I would indent the enumeration (not sure if this is needed, I did not check the compiled documentation), and leave out the enumeration for the second case.
The NotImplementedError
would be better with a ValueError("the polyhedron is not compact")
I would try to avoid using I
in the code not to overload the complex number I
...
This sentence seems to miss a word:
+ # Remove equations from incidence matrix, + # such this is the vertexfacetincidences matrix.
Otherwise, looks good!
comment:24 in reply to: ↑ 23 ; followups: ↓ 25 ↓ 26 Changed 21 months ago by
Replying to jipilab:
The
NotImplementedError
would be better with aValueError("the polyhedron is not compact")
Actually, for pyramid and bipyramid we should just return false, if not compact. No unbounded polyhedron is ever a pyramid or bipyramid.
As for prism, I think NotImplementedError
is correct.
The notion of a prism over an unbounded polyhedron makes sense and one could extend this method in a follow up.
(The rays are a bit annoying, otherwise it's the same.)
comment:25 in reply to: ↑ 24 Changed 21 months ago by
Replying to ghkliem:
Replying to jipilab:
The
NotImplementedError
would be better with aValueError("the polyhedron is not compact")
Actually, for pyramid and bipyramid we should just return false, if not compact. No unbounded polyhedron is ever a pyramid or bipyramid.
That's another option, but I thought that to return an error is more likely to be informative than a False
. This makes it evident that being a pyramid and bipyramid is a compact property and not defined for unbounded polyhedron. Returning False
means that the realm where the property exists includes the unbounded polyhedra.
That said, it is hairsplitting. I do not mind really. The only argument is that returning an error is more likely to flag errors in code rather than return False and continue in the code. For example, this may be used in try statements to detect unboundedness (ok, farfetched...)
As for prism, I think
NotImplementedError
is correct. The notion of a prism over an unbounded polyhedron makes sense and one could extend this method in a follow up. (The rays are a bit annoying, otherwise it's the same.)
That's true...
comment:26 in reply to: ↑ 24 Changed 21 months ago by
Replying to ghkliem:
Replying to jipilab:
The
NotImplementedError
would be better with aValueError("the polyhedron is not compact")
Actually, for pyramid and bipyramid we should just return false, if not compact. No unbounded polyhedron is ever a pyramid or bipyramid.
I think a ValueError
would be better than just False
. Since it is not a property of the unbounded polyhedron then it should raise an error, for the same argument jipilab gave.
As for prism, I think
NotImplementedError
is correct. The notion of a prism over an unbounded polyhedron makes sense and one could extend this method in a follow up. (The rays are a bit annoying, otherwise it's the same.)
Also agree.
I will fix these issues as suggested.
comment:27 followup: ↓ 29 Changed 21 months ago by
 Commit changed from f22fc0e032d78d46a369cd1c1712ccd0dd21532e to 5ddae4c5b617fae6eb5dfd21bdf1788a9fd2daa2
Branch pushed to git repo; I updated commit sha1. New commits:
5ddae4c  NotImplementedError > ValueError in is_pyramid and is_bipyramid

comment:28 Changed 21 months ago by
 Status changed from needs_work to needs_review
comment:29 in reply to: ↑ 27 ; followup: ↓ 31 Changed 21 months ago by
comment:30 Changed 21 months ago by
 Commit changed from 5ddae4c5b617fae6eb5dfd21bdf1788a9fd2daa2 to 27aa2e9756ab13fd826aeba25e66a3dcce6e27bf
Branch pushed to git repo; I updated commit sha1. New commits:
27aa2e9  fix a test output

comment:31 in reply to: ↑ 29 ; followup: ↓ 32 Changed 21 months ago by
Replying to ghkliem:
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
5ddae4c NotImplementedError > ValueError in is_pyramid and is_bipyramid
You need to update this in the docstring as well. There is one failing test now.
Build and run
.sage t long FILE_YOU_WORK_ON
before commiting.
I ran
./sage t long src/sage/geometry/polyhedron/base.py
and I got "All tests passed!". This command did not check the stuff in "TESTS::" section.
I will look up the problem
comment:32 in reply to: ↑ 31 Changed 21 months ago by
That's strange. You can try verbose
to see if it gets tested.
Sounds to me, as if you forgot to build after updating the code.
Replying to ghLaisRast:
Replying to ghkliem:
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
5ddae4c NotImplementedError > ValueError in is_pyramid and is_bipyramid
You need to update this in the docstring as well. There is one failing test now.
Build and run
.sage t long FILE_YOU_WORK_ON
before commiting.I ran
./sage t long src/sage/geometry/polyhedron/base.py
and I got "All tests passed!". This command did not check the stuff in "TESTS::" section. I will look up the problem
comment:33 Changed 21 months ago by
You should put an 'r' in front of the triple quotes when you put math in the docstring.
This causes some of the errors on the patchbot.
comment:34 followup: ↓ 36 Changed 21 months ago by
 Status changed from needs_review to needs_work
... and the backends should be preserved ...
comment:35 Changed 21 months ago by
 Commit changed from 27aa2e9756ab13fd826aeba25e66a3dcce6e27bf to 4480f624fdb12db3492c1214b37e45838de67d2e
Branch pushed to git repo; I updated commit sha1. New commits:
4480f62  fix docstring of is_bipyramd

comment:36 in reply to: ↑ 34 ; followup: ↓ 37 Changed 21 months ago by
 Status changed from needs_work to needs_review
Replying to jipilab:
... and the backends should be preserved ...
These functions do not return a Polyhedron object, and thus there is no backend to be changed/preserved
comment:37 in reply to: ↑ 36 Changed 21 months ago by
Replying to ghLaisRast:
Replying to jipilab:
... and the backends should be preserved ...
These functions do not return a Polyhedron object, and thus there is no backend to be changed/preserved
My bad... too many tickets at the same time...
comment:38 followup: ↓ 41 Changed 21 months ago by
 Status changed from needs_review to needs_work
A few small things:
 "polyhedron has to be compact." I would not put a period at the end of the error message.
 instead of two nested for loops with if statements, couldn't
vertices
directly be filtered and only contain the relevant ones? I would try to reduce this and try to avoid using the ifs in for loops.
 then, I would import
combinations
fromitertools
and usecombinations(vertices,2)
. This will gain some speed and be prettier.
The last two comments can be use for is_bipyramid
and is_prism
.
comment:39 Changed 21 months ago by
 Commit changed from 4480f624fdb12db3492c1214b37e45838de67d2e to 51087ecdbd64ae10369f018694e6577f8a958515
Branch pushed to git repo; I updated commit sha1. New commits:
51087ec  remove period in Error, i > i+1

comment:40 Changed 21 months ago by
 Commit changed from 51087ecdbd64ae10369f018694e6577f8a958515 to b68846aea6a1d42b727cffb5f9b9bcf1f5fcc7e4
comment:41 in reply to: ↑ 38 ; followup: ↓ 42 Changed 21 months ago by
 Status changed from needs_work to needs_review
Replying to jipilab:
A few small things:
 "polyhedron has to be compact." I would not put a period at the end of the error message.
Done
 instead of two nested for loops with if statements, couldn't
vertices
directly be filtered and only contain the relevant ones? I would try to reduce this and try to avoid using the ifs in for loops.
Done
 then, I would import
combinations
fromitertools
and usecombinations(vertices,2)
. This will gain some speed and be prettier.
It is prettier, but it is not faster, as we discussed in person. The efficiency looks very close here if I use combinations
or just two for
loops.
comment:42 in reply to: ↑ 41 Changed 21 months ago by
Replying to ghLaisRast:
Replying to jipilab:
A few small things:
 "polyhedron has to be compact." I would not put a period at the end of the error message.
Done
 instead of two nested for loops with if statements, couldn't
vertices
directly be filtered and only contain the relevant ones? I would try to reduce this and try to avoid using the ifs in for loops.Done
 then, I would import
combinations
fromitertools
and usecombinations(vertices,2)
. This will gain some speed and be prettier.It is prettier, but it is not faster, as we discussed in person. The efficiency looks very close here if I use
combinations
or just twofor
loops.
Well, it is slower? If it is as fast, it is shorter, so slightly preferable. In any case, it's not that important.
 I would apply a filter in the function
is_pyramid
for thefacets
and rename itpotential_facets
, it makes the code closer to reality... Because, why create a list withn_facets
entries when you actually do not need them at all...
 Try to name the variables in
is_bipyramid
is a way that makes the code readable:n
andm
are very generic. I would usenb_verts
andnb_facets
for example.facets
should be calledfacets_incidence
. Same withvertices
it is not a dictionary of vertices, but a dictionary giving the incidence of potential apexes.
 The code below is hard to read because of that.
a
is an index, so it could be calledindex1
. I would try to make the code as readable as possible by naming the object as consistent as possible... Especially since there is such an object calledVertex
, it may lead to confusion.
+ for a in range(len(valid_vertices)):
+ i = valid_vertices[a]
+ vertex1 = vertices[i]
+ for b in range(a+1, len(valid_vertices)):
+ j = valid_vertices[b]
+ vertex2 = vertices[j]
 Inline comments do not need to be typeset like in latex. (That's not so important... But you do not need to go to such extend...)
 The same is true about readability of
is_prism
...
comment:43 Changed 21 months ago by
 Status changed from needs_review to needs_work
comment:44 followup: ↓ 45 Changed 21 months ago by
The names should be changed to is_combinatorially_prism
and is_combinatorially_bipyramid
(is_pyramid
is fine of course).
See also #28256.
comment:45 in reply to: ↑ 44 ; followups: ↓ 46 ↓ 49 Changed 21 months ago by
Replying to ghkliem:
The names should be changed to
is_combinatorially_prism
andis_combinatorially_bipyramid
(is_pyramid
is fine of course).See also #28256.
No. I disagree. It is not "just because" it is a combinatorial property that we should pollute the name space. The functions in this ticket are obviously combinatorial ones (where could a confusion come from? and imagine how complicated a geometric verification of this could be...), whereas the method in #28256 has an obvious possibility to be mistaken for the geometric polar dual.
Let's not overdo things and be more catholic than the pope...
comment:46 in reply to: ↑ 45 ; followup: ↓ 47 Changed 21 months ago by
Replying to jipilab:
Replying to ghkliem:
The names should be changed to
is_combinatorially_prism
andis_combinatorially_bipyramid
(is_pyramid
is fine of course).See also #28256.
No. I disagree. It is not "just because" it is a combinatorial property that we should pollute the name space. The functions in this ticket are obviously combinatorial ones (where could a confusion come from? and imagine how complicated a geometric verification of this could be...), whereas the method in #28256 has an obvious possibility to be mistaken for the geometric polar dual.
The geometric verification is really easy. For the prism you just check, that the pairs of vertices all differ by a common vector. For the bipyramid you check that all vertices but the two apices lie on a common hyperplane.
Let's not overdo things and be more catholic than the pope...
I'm confused. I find the distinction between prism and only combinatorially equivalent to prism very natural. Just like the distinction between two polytopes being exactly polar to each other or just up to combinatorially equivalence.
I don't see why the second thing is more natural than the first one.
comment:47 in reply to: ↑ 46 Changed 21 months ago by
Replying to ghkliem:
Replying to jipilab:
Replying to ghkliem:
The names should be changed to
is_combinatorially_prism
andis_combinatorially_bipyramid
(is_pyramid
is fine of course).See also #28256.
No. I disagree. It is not "just because" it is a combinatorial property that we should pollute the name space. The functions in this ticket are obviously combinatorial ones (where could a confusion come from? and imagine how complicated a geometric verification of this could be...), whereas the method in #28256 has an obvious possibility to be mistaken for the geometric polar dual.
The geometric verification is really easy. For the prism you just check, that the pairs of vertices all differ by a common vector.
No. The realization space of prism is more complicated. Namely, checking what you did, you still have lots of freedom for each face, in particular, there are 2d
degrees of freedom for the normal of the two opposite facets defining the prism. Polytopes in higher dimension are not as easy as in 3d. One should agree on what one means by a geometric prism before, and there are several ways to define one. The one in this ticket is the combinatorial one.
If you want to get into tons of subtleties like projective/linear/affine equivalence and all those sorts of definitions for every single constructions, you may, but it is not the point here.
For the bipyramid you check that all vertices but the two apices lie on a common hyperplane.
This way to verify bipyramid is so artificial that I can not imagine a usage. Anyhow, it is not the point of the current ticket. Of course, if you feel like this is an absolute necessity, then you may create a followup ticket.
Let's not overdo things and be more catholic than the pope...
I'm confused. I find the distinction between prism and only combinatorially equivalent to prism very natural.
The distinction is clear. The ticket is about combinatorial check. Let's just limit this ticket on this, please.
comment:48 Changed 21 months ago by
I'm going to do some work on this.
comment:49 in reply to: ↑ 45 Changed 21 months ago by
Replying to ghkliem:
I'm going to do some work on this.
Ok.
Replying to jipilab:
Well, it is slower? If it is as fast, it is shorter, so slightly preferable. In any case, it's not that important.
Using two for
loops is (very) slightly faster than using combinations
, and that is why I chose the two for
loops. I guess since combinations
makes the code prettier and more readable, you are right, it is preferable. ghkliem can look at the commit "e41a64f" to see the code using combinations
if he would like to.
Replying to jipilab:
Replying to ghkliem:
The names should be changed to
is_combinatorially_prism
andis_combinatorially_bipyramid
(is_pyramid
is fine of course).See also #28256.
No. I disagree. It is not "just because" it is a combinatorial property that we should pollute the name space. The functions in this ticket are obviously combinatorial ones (where could a confusion come from? and imagine how complicated a geometric verification of this could be...), whereas the method in #28256 has an obvious possibility to be mistaken for the geometric polar dual.
A confusion could arise if the user thought that P.is_bipyramid() == True
means that we can construct (the geometric polytope) P
as a bipyramid over some polytope on the vertices of P
, which is not the case here. A typical example, shown below, is if you start with the regular octahedron and perturbed one of its vertices such that you still have an octahedron. Then P.is_bipyramid
gives True
. However, you can not construct P
as a bipyramid using the given certificate.
sage: V = [[1, 0, 0], [1, 0, 0], [1/2, 1, 0], [0, 1, 0], [0, 0, 1], [0, 0, 1]] sage: P = Polyhedron(V) sage: P.is_combinatorially_isomorphic(polytopes.octahedron()) True sage: P.is_bipyramid(certificate=True) (True, [A vertex at (1, 0, 0), A vertex at (1, 0, 0)]) sage: Q = Polyhedron([V[i] for i in [2,3,4,5]]); Q A 3dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices
This confusion could be dealt with if the user read the documentation of the method which says
Test whether the polytope is combinatorially equivalent to a bipyramid over some polytope.
In all, I think here it should be is_combinatorially_bipyramid
and is_combinatorially_prism
, if we want to remove the confusion.
comment:50 Changed 21 months ago by
 Commit changed from b68846aea6a1d42b727cffb5f9b9bcf1f5fcc7e4 to 3ae3c03e0f96b2221b9872226c91101b33c80b06
Branch pushed to git repo; I updated commit sha1. New commits:
3ae3c03  improved readability

comment:51 Changed 21 months ago by
 Status changed from needs_work to needs_review
comment:53 Changed 20 months ago by
 Branch changed from public/27689bis to public/27689new
 Commit changed from 3ae3c03e0f96b2221b9872226c91101b33c80b06 to 5764ce4f3d48c6a9969211a94429c28a305b7345
 Status changed from needs_work to needs_review
New commits:
5764ce4  implemented is_pyramid, is_bipyramid, is_prism

comment:54 Changed 20 months ago by
 Reviewers set to JeanPhilippe Labbé
 Status changed from needs_review to positive_review
This looks good to me. I looked for a nonascii character, but could not find one...
comment:55 Changed 20 months ago by
 Branch changed from public/27689new to 5764ce4f3d48c6a9969211a94429c28a305b7345
 Resolution set to fixed
 Status changed from positive_review to closed
Somehow all those methods should move to
CombinatorialPolyhedron
(#26887) eventually. However, this might take some time until it actually happens.weather > whether
is_pyramid
is_bipyramid
##
>#
Polyhedron(vertices=[[]]).is_pyramid
will yieldFalse
, asincidence_matrix
is not what one would expect in this caseWe should do changes in
pyramid
as well:
pyramid
should not be defined for unbounded polyhedra, this will not yield the convex hull (the convex hull is not even closed)Polyhedron().pyramid()
does not work, but should yield the 0dimensional polytopetow
>two
At the moment I'm not sure whether the code for bipyramide and prism is correct. I have to think about it. There might be some weird counterexample in high dimensions.
I think one should do prism in the following way:
A polytope is a prism if we find facets F_1,F_2 with vertices x_1,...,x_n resp. y_1,...,y_n such that they are exactly all vertices (so far so good).
Also they can be labeled (as I indicated) such that for each other facet either x_i and y_i are contained in it or neither.
To find this labeling is a nontrivial combinatorial task, I would say.
Basically we want to know whether a bipartite graph has a perfect matching.
For the bipyramid we do the dual approach.