Opened 8 months ago

Closed 8 months ago

#28256 closed enhancement (fixed)

add .is_self_dual method for polytopes

Reported by: gh-LaisRast Owned by:
Priority: major Milestone: sage-8.9
Component: geometry Keywords: self-dual, polytope, dual, days100
Cc: jipilab, gh-kliem Merged in:
Authors: Laith Rastanawi Reviewers: Simon King
Report Upstream: N/A Work issues:
Branch: 11041eb (Commits) Commit: 11041eb15ace7bc597935488a535f951731eedc6
Dependencies: Stopgaps:

Description

A polytope is self-dual 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 self-dual.

Change History (20)

comment:1 Changed 8 months ago by gh-LaisRast

  • Branch set to public/28256
  • Commit set to 28bf771a9af366e08fc3a1771e5ef266208a6947
  • Status changed from new to needs_review

New commits:

28bf771implement is_self_dual for polytopes

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

Please have in mind that the check should also work for non-fulldimensional polyhedra (e.g. Simplex).

Unfortunately, git.sagemath is down at the moment, so I don't see your code.

comment:3 Changed 8 months ago by gh-kliem

Never mind.

comment:4 in reply to: ↑ 2 Changed 8 months ago by gh-LaisRast

Replying to gh-kliem:

Please have in mind that the check should also work for non-fulldimensional polyhedra (e.g. Simplex).

Unfortunately, git.sagemath is down at the moment, so I don't see your code.

It does work for non-full dimensional polytopes. The 3-simplex (a positive example) and the 2nd 4-hypersimplex (a negative example) are already in the doctest.

comment:5 follow-ups: Changed 8 months ago by gh-kliem

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

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 8 months ago by gh-kliem

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 8 months ago by gh-LaisRast

Replying to gh-kliem:

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

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 8 months ago by git

  • Commit changed from 28bf771a9af366e08fc3a1771e5ef266208a6947 to 11041eb15ace7bc597935488a535f951731eedc6

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

11041ebalgorithm uses vertex-facet graph and its reversed-direction copy

comment:10 Changed 8 months ago by gh-kliem

This looks good to me now (remember that I haven't tested this on a computer).

comment:11 Changed 8 months ago by SimonKing

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

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 8 months ago by gh-kliem

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 8 months ago by jipilab

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 ; follow-up: Changed 8 months ago by gh-kliem

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

comment:17 in reply to: ↑ 16 Changed 8 months ago by jipilab

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 8 months ago by gh-LaisRast

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 inclusion-reversing 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 self-polarity: A subset A of R^d is self-polar 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, Self-polar polytopes https://arxiv.org/pdf/1902.00784.pdf

comment:19 Changed 8 months ago by gh-kliem

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 self-dual 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 8 months ago by vbraun

  • Branch changed from public/28256 to 11041eb15ace7bc597935488a535f951731eedc6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.