Implement is_pyramid, is_bipyramid, is_prism for polytopes

[gh-LaisRast]

Implement the following methods in geometry/polyhedron/base.py:

• is_pyramid: test whether the polytope is a pyramid over one of its facets
• is_bipyramid: test whether the polytope is combinatorially equivalent to a bipyramid over some polytope
• is_prism: test whether the polytope is combinatorially equivalent to a prism of some polytope

[gh-kliem]

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 yield False, as incidence_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 0-dimensional 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 non-trivial 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.

[gh-kliem]

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.

[gh-kliem]

Replying to gh-kliem:

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.

[git]

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

​76caa3e

typos and change the certificate of is_pyramid

[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

[gh-LaisRast]

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 gh-kliem:

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 yield False, as incidence_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 0-dimensional 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 non-trivial 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.

[gh-LaisRast]

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

[git]

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

​9db57df

delete empty lines

[jipilab]

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.

[gh-kliem]

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 5-dimensional permutahedron on my machine, 5s for the 9-dimensional cube).

This is what one should do for the bipyramid:

1. Let a,b the candidates for the apexes of a polytope P.
2. P is a bipyramid over a and b, if and only if the vertex figures are identical.

Hence we can take all facets incident to a in their vertex-representation 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 facet-incidences of vertices/edges.

[jipilab]

Replying to gh-kliem:

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 5-dimensional permutahedron on my machine, 5s for the 9-dimensional 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:

1. Let a,b the candidates for the apexes of a polytope P.
2. P is a bipyramid over a and b, 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 vertex-representation 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 facet-incidences of vertices/edges.

--> I don't understand what this is doing.

[gh-kliem]

Replying to jipilab:

Replying to gh-kliem:

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 5-dimensional permutahedron on my machine, 5s for the 9-dimensional 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.

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:

1. Let a,b the candidates for the apexes of a polytope P.
2. P is a bipyramid over a and b, 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 vertex-incidences. 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 vertex-representation 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 facet-incidences of vertices/edges.

--> I don't understand what this is doing.

[jipilab]

Replying to gh-kliem:

Replying to jipilab:

Replying to gh-kliem:

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 5-dimensional permutahedron on my machine, 5s for the 9-dimensional 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.

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 vertex-incidences. 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 centrally-symmetric 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.

[gh-kliem]

Replying to jipilab:

Replying to gh-kliem:

Replying to jipilab:

Replying to gh-kliem:

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 5-dimensional permutahedron on my machine, 5s for the 9-dimensional 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.

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 vertex-facet 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 vertex-facet-incidences 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 vertex-incidences. 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 centrally-symmetric 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.

[embray]

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

[gh-kliem]

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?

[gh-kliem]

---

New commits:

​8b67a7e	Merge branch 'public/27689' of git://trac.sagemath.org/sage into public/27689-bis
​513d852	is_bipyramid and is_prism should now be working

[gh-LaisRast]

resolving conflicts

[git]

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

​f22fc0e

Merge branch 'public/27689-bis' of git://trac.sagemath.org/sage into is_bipyramid

[jipilab]

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 vertex-facet-incidences matrix.

Otherwise, looks good!

[gh-kliem]

Replying to jipilab:

The NotImplementedError would be better with a ValueError("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.)

[jipilab]

Replying to gh-kliem:

Replying to jipilab:

The NotImplementedError would be better with a ValueError("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, far-fetched...)

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

[gh-LaisRast]

Replying to gh-kliem:

Replying to jipilab:

The NotImplementedError would be better with a ValueError("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.

[git]

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

​5ddae4c

NotImplementedError -> ValueError in is_pyramid and is_bipyramid

[gh-kliem]

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.

[git]

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

​27aa2e9

fix a test output

[gh-LaisRast]

Replying to gh-kliem:

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

[gh-kliem]

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 gh-LaisRast:

Replying to gh-kliem:

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

[jipilab]

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.

[jipilab]

... and the backends should be preserved ...

[git]

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

​4480f62

fix docstring of is_bipyramd

[gh-LaisRast]

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

[jipilab]

Replying to gh-LaisRast:

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

[jipilab]

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 from itertools and use combinations(vertices,2). This will gain some speed and be prettier.

The last two comments can be use for is_bipyramid and is_prism.

[git]

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

​51087ec

remove period in Error, i -> i+1

[git]

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

​e41a64f	filter vertices in advance and use combinations instead of two for loops
​b68846a	back to two for loops

[gh-LaisRast]

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 from itertools and use combinations(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.

[jipilab]

Replying to gh-LaisRast:

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 from itertools and use combinations(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.

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 the facets and rename it potential_facets, it makes the code closer to reality... Because, why create a list with n_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 and m are very generic. I would use nb_verts and nb_facets for example. facets should be called facets_incidence. Same with vertices 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 called index1. 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 called Vertex, 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...

[gh-kliem]

The names should be changed to is_combinatorially_prism and is_combinatorially_bipyramid (is_pyramid is fine of course).

See also #28256.

[jipilab]

Replying to gh-kliem:

The names should be changed to is_combinatorially_prism and is_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...

[gh-kliem]

Replying to jipilab:

Replying to gh-kliem:

The names should be changed to is_combinatorially_prism and is_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.

[jipilab]

Replying to gh-kliem:

Replying to jipilab:

Replying to gh-kliem:

The names should be changed to is_combinatorially_prism and is_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 follow-up 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.

[gh-kliem]

I'm going to do some work on this.

[gh-LaisRast]

Replying to gh-kliem:

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. gh-kliem can look at the commit "e41a64f" to see the code using combinations if he would like to.

Replying to jipilab:

Replying to gh-kliem:

The names should be changed to is_combinatorially_prism and is_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 3-dimensional 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.

[git]

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

​3ae3c03

improved readability

[jipilab]

Conflict.

[gh-kliem]

New commits:

​5764ce4

implemented is_pyramid, is_bipyramid, is_prism

[jipilab]

This looks good to me. I looked for a non-ascii character, but could not find one...