Opened 21 months ago
Closed 21 months ago
#28256 closed enhancement (fixed)
add .is_self_dual method for polytopes
Reported by:  ghLaisRast  Owned by:  

Priority:  major  Milestone:  sage8.9 
Component:  geometry  Keywords:  selfdual, polytope, dual, days100 
Cc:  jipilab, ghkliem  Merged in:  
Authors:  Laith Rastanawi  Reviewers:  Simon King 
Report Upstream:  N/A  Work issues:  
Branch:  11041eb (Commits, GitHub, GitLab)  Commit:  11041eb15ace7bc597935488a535f951731eedc6 
Dependencies:  Stopgaps: 
Description
A polytope is selfdual if its face lattice is isomorphic to the face lattice of its dual polytope.
In this tickets I will add is_self_dual
method to the Polyhedron
class to check (combinatorially) if a polytope is selfdual.
Change History (20)
comment:1 Changed 21 months ago by
 Branch set to public/28256
 Commit set to 28bf771a9af366e08fc3a1771e5ef266208a6947
 Status changed from new to needs_review
comment:2 followup: ↓ 4 Changed 21 months ago by
Please have in mind that the check should also work for nonfulldimensional polyhedra (e.g. Simplex).
Unfortunately, git.sagemath is down at the moment, so I don't see your code.
comment:3 Changed 21 months ago by
Never mind.
comment:4 in reply to: ↑ 2 Changed 21 months ago by
Replying to ghkliem:
Please have in mind that the check should also work for nonfulldimensional polyhedra (e.g. Simplex).
Unfortunately, git.sagemath is down at the moment, so I don't see your code.
It does work for nonfull dimensional polytopes. The 3simplex (a positive example) and the 2nd 4hypersimplex (a negative example) are already in the doctest.
comment:5 followups: ↓ 6 ↓ 8 Changed 21 months ago by
Instead of testing whether the matrix is square, I would check first thing that n_facets
equals n_vertices
(incidence matrix does take some time).
The approach seems somewhat hacky. How about taking the vertex_facet_graph
and checking that it is isomorphic to its reverse (I assume that isomorphism does distinct directions, didn't ckeck).
comment:6 in reply to: ↑ 5 Changed 21 months ago by
The approach seems somewhat hacky. How about taking the
vertex_facet_graph
and checking that it is isomorphic to its reverse (I assume that isomorphism does distinct directions, didn't ckeck).
I'd rather qualify this as a clever algorithm. This gets rid of automorphisms of the polytope directly while you will have to deal with them in the oriented graphs. The complexity should be exactly the same and most likely equivalent, because adding the special vertex is equivalent to specify the orientation.
Now, I do not know how isomorphism of graphs is preparsing things, but most likely there is something dealing with bipartite graphs.
comment:7 Changed 21 months ago by
Replying to jipilab:
The approach seems somewhat hacky. How about taking the
vertex_facet_graph
and checking that it is isomorphic to its reverse (I assume that isomorphism does distinct directions, didn't ckeck).I'd rather qualify this as a clever algorithm. This gets rid of automorphisms of the polytope directly while you will have to deal with them in the oriented graphs. The complexity should be exactly the same and most likely equivalent, because adding the special vertex is equivalent to specify the orientation.
Yes, most likely both approaches take almost the same time.
I just figured, it's a lot of lines to create a graph that is basically the vertex_facet_graph
.
Instead of the current approach, I find some prechecking and
G1 = self.vertex_facet_graph() G2 = G1.reverse() return G1.is_isomorphic(G2)
to be more transparent.
Now, I do not know how isomorphism of graphs is preparsing things, but most likely there is something dealing with bipartite graphs.
comment:8 in reply to: ↑ 5 Changed 21 months ago by
Replying to ghkliem:
Instead of testing whether the matrix is square, I would check first thing that
n_facets
equalsn_vertices
(incidence matrix does take some time).
Agree
The approach seems somewhat hacky. How about taking the
vertex_facet_graph
and checking that it is isomorphic to its reverse (I assume that isomorphism does distinct directions, didn't ckeck).
It turns out that 'is_isomorphic' does see the directions. So less lines and more readable code.
comment:9 Changed 21 months ago by
 Commit changed from 28bf771a9af366e08fc3a1771e5ef266208a6947 to 11041eb15ace7bc597935488a535f951731eedc6
Branch pushed to git repo; I updated commit sha1. New commits:
11041eb  algorithm uses vertexfacet graph and its reverseddirection copy

comment:10 Changed 21 months ago by
This looks good to me now (remember that I haven't tested this on a computer).
comment:11 Changed 21 months ago by
 Reviewers set to Simon King
 Status changed from needs_review to positive_review
The pyflakes plugin complains. But apparently it only complains about lines that aren't touched by the patch and thus shouldn't be a problem for this ticket.
Tests on a patchbot pass. And the code and docs look good to me. I believe this can constitute a positive review.
comment:12 followups: ↓ 13 ↓ 14 ↓ 15 ↓ 18 Changed 21 months ago by
Shouldn't this method be called is_combinatorially_self_dual
to distinguish the tested property from geometric self duality (self polarity)?
comment:13 in reply to: ↑ 12 Changed 21 months ago by
Replying to mkoeppe:
Shouldn't this method be called
is_combinatorially_self_dual
to distinguish the tested property from geometric self duality (self
What do you mean by geometric self duality?
From many ways one could distinguish polyhedra Sage only knows identical and combinatorially equivalent, doesn't it (affinely equivalent and projectively would make sense as well, but I couldn't find this anywhere).
For self duality being exactly self dual doesn't make any sense (once we are at least 2 dimensional). So I would figure the question is a combinatorial one.
In #27689, on the other hand we check of a polyhedron is a prism etc. Here it makes sense to ask for exactly and up to combinatorially equivalence. Maybe one could provide a keyword for cases, where the question has multiple meanings.
comment:14 in reply to: ↑ 12 Changed 21 months ago by
Replying to mkoeppe:
Shouldn't this method be called
is_combinatorially_self_dual
to distinguish the tested property from geometric self duality (self polarity)?
+1
I would vote to simply rename the function to that. It is a combinatorial self duality and should not be confused with the eventual property that self.polar() == self
.
comment:15 in reply to: ↑ 12 ; followup: ↓ 16 Changed 21 months ago by
Replying to mkoeppe:
Shouldn't this method be called
is_combinatorially_self_dual
to distinguish the tested property from geometric self duality (self polarity)?
+1
Convinced.
Btw, potentially there is also the method is_combinatorially_dual(self, other)
. Here, specifying 'combinatorially' is even more important. One should name this ticket's method consistently. (Even though checking for self polarity is probably not worth a method.)
comment:16 in reply to: ↑ 15 ; followup: ↓ 17 Changed 21 months ago by
Btw, potentially there is also the method
is_combinatorially_dual(self, other)
. Here, specifying 'combinatorially' is even more important. One should name this ticket's method consistently. (Even though checking for self polarity is probably not worth a method.)
A compact polyhedron is always dual to another one using polarity. So this name is incomplete, the self is important there.
comment:17 in reply to: ↑ 16 Changed 21 months ago by
Replying to jipilab:
Btw, potentially there is also the method
is_combinatorially_dual(self, other)
. Here, specifying 'combinatorially' is even more important. One should name this ticket's method consistently. (Even though checking for self polarity is probably not worth a method.)A compact polyhedron is always dual to another one using polarity. So this name is incomplete, the self is important there.
Oops, my bad. Didn't see the other
.
I would say that this could be done in a different ticket, if someone expresses the need.
comment:18 in reply to: ↑ 12 Changed 21 months ago by
Replying to mkoeppe:
Shouldn't this method be called
is_combinatorially_self_dual
to distinguish the tested property from geometric self duality (self polarity)?
I would still vote for leaving it as is_self_dual
instead of is_combinatorially_self_dual
.
I am following the convention that duality is defined for abstract polytopes (face lattices), while polarity is defined for geometric realizations of polytopes (and more generally any subset of an Euclidean space).
For that you can refer to Grünbaum's book (Convex Ptolytopes). In section 3.4, he defined two (geometric realizations of two) polytopes to be dual to each other if there is an inclusionreversing bijection between their face lattices. And later, in the same section, he defined polarity for geometric polytopes by the well know definition.
On the other hand, for is_self_polar
, since The only set A
for which A == A.polar()
is the unit ball (Theorem 3.1 of [1]), the definition should be more loosely than what is suggested. In [1], this is the definition of selfpolarity:
A subset A
of R^d
is selfpolar provided there exists some orthogonal transformation U
of R^d
such that A = U*A.polar()
.
This is of course can be done in a different ticket.
[1]: Alathea Jensen, Selfpolar polytopes https://arxiv.org/pdf/1902.00784.pdf
comment:19 Changed 21 months ago by
I'm totally confused by now and don't know what to think.
I figured we name everything that can be confused with the combinatorially
prefix.
Now in #27689, JP voted against that.
If find the property selfdual far less ambiguous as being a prism.
The name is_combinatorially_self_dual
is also hard to find via tab completion.
Overall, I think people with stronger opinions on names than me should decide.
comment:20 Changed 21 months ago by
 Branch changed from public/28256 to 11041eb15ace7bc597935488a535f951731eedc6
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
implement is_self_dual for polytopes