Implement is_pyramid, is_bipyramid, is_prism for polytopes

[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

CC: @jplab @kliem

Component: geometry

Keywords: polytopes, pyramid, bipyramid, prism, days100

Author: Laith Rastanawi, Jonathan Kliem

Branch/Commit: 5764ce4

Reviewer: Jean-Philippe Labbé

Issue created by migration from https://trac.sagemath.org/ticket/27689

[LaisRast]

Branch: public/27689

[LaisRast]

Commit: 41b554b

[kliem]

comment:2

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.

[kliem]

comment:3

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.

[kliem]

comment:4

Replying to @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.

[sagetrac-git]

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

76caa3e

typos and change the certificate of is_pyramid

[sagetrac-git]

Changed commit from 41b554b to 76caa3e

[sagetrac-git]

Changed commit from 76caa3e to b67c9ae

[sagetrac-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

[LaisRast]

comment:7

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