Opened 12 months ago

Closed 7 months ago

#27689 closed enhancement (fixed)

Implement is_pyramid, is_bipyramid, is_prism for polytopes

Reported by: gh-LaisRast Owned by:
Priority: major Milestone: sage-8.9
Component: geometry Keywords: polytopes, pyramid, bipyramid, prism, days100
Cc: jipilab, gh-kliem Merged in:
Authors: Laith Rastanawi, Jonathan Kliem Reviewers: Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: 5764ce4 (Commits) Commit: 5764ce4f3d48c6a9969211a94429c28a305b7345
Dependencies: Stopgaps:

Description (last modified by gh-kliem)

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

Change History (55)

comment:1 Changed 12 months ago by gh-LaisRast

  • Branch set to public/27689
  • Commit set to 41b554bd54eab1775b0e0b479a8e9c8af326b2bf
  • Status changed from new to needs_review

comment:2 follow-up: Changed 12 months ago by 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.

comment:3 follow-up: Changed 12 months ago by 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.

comment:4 in reply to: ↑ 3 Changed 12 months ago by 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.

comment:5 Changed 12 months ago by git

  • Commit changed from 41b554bd54eab1775b0e0b479a8e9c8af326b2bf to 76caa3eca94e38207d84e2ff5f5d55ceb70bbc08

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

76caa3etypos and change the certificate of is_pyramid

comment:6 follow-up: Changed 12 months ago by git

  • Commit changed from 76caa3eca94e38207d84e2ff5f5d55ceb70bbc08 to b67c9ae531d44d8e5d52348f6a3aa5b83788898e

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

b67c9aeremove x = None in change_ring so that pyflakes stops showing error

comment:7 in reply to: ↑ 2 Changed 12 months ago by gh-LaisRast

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

Last edited 12 months ago by gh-LaisRast (previous) (diff)

comment:8 in reply to: ↑ 6 Changed 12 months ago by 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:

b67c9aeremove x = None in change_ring so that pyflakes stops showing error

comment:9 Changed 12 months ago by git

  • Commit changed from b67c9ae531d44d8e5d52348f6a3aa5b83788898e to 9db57df9790d6936da398d09744c57e5347650a6

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

9db57dfdelete empty lines

comment:10 Changed 12 months ago by 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.

comment:11 follow-up: Changed 12 months ago by 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.

comment:12 in reply to: ↑ 11 ; follow-up: Changed 12 months ago by 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.

Last edited 12 months ago by jipilab (previous) (diff)

comment:13 in reply to: ↑ 12 ; follow-up: Changed 12 months ago by 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.

comment:14 in reply to: ↑ 13 ; follow-up: Changed 12 months ago by 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.

Last edited 12 months ago by jipilab (previous) (diff)

comment:15 in reply to: ↑ 14 Changed 12 months ago by 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.

comment:16 Changed 10 months ago by embray

  • Milestone changed from sage-8.8 to sage-8.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 10 months ago by 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?

comment:18 Changed 10 months ago by gh-kliem

  • Description modified (diff)

comment:19 Changed 10 months ago by gh-kliem

  • Authors changed from Laith Rastanawi to Laith Rastanawi, Jonathan Kliem
  • Branch changed from public/27689 to public/27689-bis
  • Commit changed from 9db57df9790d6936da398d09744c57e5347650a6 to 513d852550386bd498056c17a6ce37134915e029
  • Status changed from needs_work to needs_review

New commits:

8b67a7eMerge branch 'public/27689' of git://trac.sagemath.org/sage into public/27689-bis
513d852is_bipyramid and is_prism should now be working

comment:20 Changed 9 months ago by gh-LaisRast

  • Keywords days100 added
  • Status changed from needs_review to needs_work

resolving conflicts

comment:21 Changed 9 months ago by git

  • Commit changed from 513d852550386bd498056c17a6ce37134915e029 to f22fc0e032d78d46a369cd1c1712ccd0dd21532e

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

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

comment:22 Changed 9 months ago by gh-LaisRast

  • Status changed from needs_work to needs_review

comment:23 follow-up: Changed 9 months ago by jipilab

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

Otherwise, looks good!

comment:24 in reply to: ↑ 23 ; follow-ups: Changed 9 months ago by 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.)

comment:25 in reply to: ↑ 24 Changed 9 months ago by 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...

comment:26 in reply to: ↑ 24 Changed 9 months ago by 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.

comment:27 follow-up: Changed 9 months ago by git

  • Commit changed from f22fc0e032d78d46a369cd1c1712ccd0dd21532e to 5ddae4c5b617fae6eb5dfd21bdf1788a9fd2daa2

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

5ddae4cNotImplementedError -> ValueError in is_pyramid and is_bipyramid

comment:28 Changed 9 months ago by gh-LaisRast

  • Status changed from needs_work to needs_review

comment:29 in reply to: ↑ 27 ; follow-up: Changed 9 months ago by gh-kliem

Replying to git:

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

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

comment:30 Changed 9 months ago by git

  • Commit changed from 5ddae4c5b617fae6eb5dfd21bdf1788a9fd2daa2 to 27aa2e9756ab13fd826aeba25e66a3dcce6e27bf

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

27aa2e9fix a test output

comment:31 in reply to: ↑ 29 ; follow-up: Changed 9 months ago by gh-LaisRast

Replying to gh-kliem:

Replying to git:

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

5ddae4cNotImplementedError -> 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 9 months ago by 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:

5ddae4cNotImplementedError -> 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 9 months ago by 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.

comment:34 follow-up: Changed 9 months ago by jipilab

  • Status changed from needs_review to needs_work

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

comment:35 Changed 9 months ago by git

  • Commit changed from 27aa2e9756ab13fd826aeba25e66a3dcce6e27bf to 4480f624fdb12db3492c1214b37e45838de67d2e

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

4480f62fix docstring of is_bipyramd

comment:36 in reply to: ↑ 34 ; follow-up: Changed 9 months ago by gh-LaisRast

  • 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 9 months ago by 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...

comment:38 follow-up: Changed 9 months ago by jipilab

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

comment:39 Changed 9 months ago by git

  • Commit changed from 4480f624fdb12db3492c1214b37e45838de67d2e to 51087ecdbd64ae10369f018694e6577f8a958515

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

51087ecremove period in Error, i -> i+1

comment:40 Changed 9 months ago by git

  • Commit changed from 51087ecdbd64ae10369f018694e6577f8a958515 to b68846aea6a1d42b727cffb5f9b9bcf1f5fcc7e4

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

e41a64ffilter vertices in advance and use combinations instead of two for loops
b68846aback to two for loops

comment:41 in reply to: ↑ 38 ; follow-up: Changed 9 months ago by gh-LaisRast

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

comment:42 in reply to: ↑ 41 Changed 8 months ago by 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...

comment:43 Changed 8 months ago by jipilab

  • Status changed from needs_review to needs_work

comment:44 follow-up: Changed 8 months ago by gh-kliem

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 ; follow-ups: Changed 8 months ago by 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...

comment:46 in reply to: ↑ 45 ; follow-up: Changed 8 months ago by 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.

comment:47 in reply to: ↑ 46 Changed 8 months ago by 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.

comment:48 Changed 8 months ago by gh-kliem

I'm going to do some work on this.

comment:49 in reply to: ↑ 45 Changed 8 months ago by 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.

comment:50 Changed 8 months ago by git

  • Commit changed from b68846aea6a1d42b727cffb5f9b9bcf1f5fcc7e4 to 3ae3c03e0f96b2221b9872226c91101b33c80b06

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

3ae3c03improved readability

comment:51 Changed 8 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:52 Changed 8 months ago by jipilab

  • Status changed from needs_review to needs_work

Conflict.

comment:53 Changed 8 months ago by gh-kliem

  • Branch changed from public/27689-bis to public/27689-new
  • Commit changed from 3ae3c03e0f96b2221b9872226c91101b33c80b06 to 5764ce4f3d48c6a9969211a94429c28a305b7345
  • Status changed from needs_work to needs_review

New commits:

5764ce4implemented is_pyramid, is_bipyramid, is_prism

comment:54 Changed 8 months ago by jipilab

  • Reviewers set to Jean-Philippe Labbé
  • Status changed from needs_review to positive_review

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

comment:55 Changed 7 months ago by vbraun

  • Branch changed from public/27689-new to 5764ce4f3d48c6a9969211a94429c28a305b7345
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.