Opened 18 months ago
Closed 17 months ago
#29127 closed enhancement (fixed)
Implement an affine basis for polytopes
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.1 
Component:  geometry  Keywords:  polytopes, affine basis 
Cc:  jipilab, ghLaisRast  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  Laith Rastanawi 
Report Upstream:  N/A  Work issues:  
Branch:  ba31a5e (Commits, GitHub, GitLab)  Commit:  ba31a5e505bb23ca2de502250bcc98352b66446b 
Dependencies:  #29117  Stopgaps: 
Description (last modified by )
Sometimes it is useful to obtain dim + 1
vertices of a polytope in general position  an affine basis.
With #29117, which provides a maximal chain of faces, we can easily obtain those vertices that are even guaranteed to be in general position for any realization of the polytope.
We apply this affine basis to simplify is_inscribed
. This is also faster, as the current approach requires to compute all neighbors of a vertex (which can be pretty hard, even once this is done efficiently through combinatorial polyhedron):
Time without this ticket:
sage: P = polytopes.hypercube(8) sage: %time P.is_inscribed() CPU times: user 17.5 s, sys: 32.4 ms, total: 17.5 s Wall time: 17.5 s True
Time with this ticket:
sage: P = polytopes.hypercube(8) sage: %time P.is_inscribed() CPU times: user 17.5 ms, sys: 10 µs, total: 17.5 ms Wall time: 17.4 ms True
While we are at it, we fix a bug for the empty polyhedron, so that a_maximal_chain
returns just a list of one empty face, instead of two.
Follow ups:
 We use this to fix #29116.
 We implement
is_affinely_isomorphic
.
Change History (12)
comment:1 Changed 18 months ago by
 Description modified (diff)
comment:2 Changed 18 months ago by
 Branch set to public/29127
 Commit set to 231c16f3a948591183cf21bfff83226997201fea
 Status changed from new to needs_review
comment:3 Changed 18 months ago by
 Commit changed from 231c16f3a948591183cf21bfff83226997201fea to 4fb0f6ba4cfd36da8f5f41a499c78aa82cccca4b
Branch pushed to git repo; I updated commit sha1. New commits:
4fb0f6b  handling smalldimensional cases

comment:4 Changed 18 months ago by
 Branch changed from public/29127 to public/29127reb
 Commit changed from 4fb0f6ba4cfd36da8f5f41a499c78aa82cccca4b to d2d2a8a4ebc544f986cb38744eee91047371bca6
New commits:
61dd4a5  implement `a_maximal_chain` for combinatorial polyhedron

a18011f  improved documentation

2e9f25f  exposed a_maximal_chain to polyhedron_base

0315652  implement `an_affine_basis` for polytopes

554556d  more description in the docs

aa30035  used an_affine_basis to simplify is_inscribed

08b263e  apply change to 29125

d2d2a8a  handling smalldimensional cases

comment:5 Changed 18 months ago by
 Dependencies changed from #29117, #29125 to #29117
comment:6 Changed 17 months ago by
 Status changed from needs_review to needs_work
Some typos
 in the face lattices and picking for each cover relation  on vertex that is in the difference. Thus this method + in the face lattice and picking for each cover relationa + one vertex that is in the difference. Thus this method
# We just in the folling that element in ``chain_indices`` is a sorted list # of Vindices.
Since you also implemented an_affine_basis for Polyhedron, maybe it is better to use it. Doing so, you can remove the following part of your code and thus making the code easier to read. I am saying this because if you use an_affine_basis for Polyhedron, you will have the whole polyhedron as a face.
# Finally append some vertex not contained in ``face``, # which is a facet of ``self`` now. for i in range(len(face)): if face[i] != i: basis_indices.append(i) break else: # no break basis_indices.append(len(face)) +}}}
comment:7 Changed 17 months ago by
 Description modified (diff)
comment:8 Changed 17 months ago by
 Commit changed from d2d2a8a4ebc544f986cb38744eee91047371bca6 to b5f9be530140ad827cbdec2164103a44dc4caaf9
comment:9 Changed 17 months ago by
 Status changed from needs_work to needs_review
comment:10 Changed 17 months ago by
 Commit changed from b5f9be530140ad827cbdec2164103a44dc4caaf9 to ba31a5e505bb23ca2de502250bcc98352b66446b
Branch pushed to git repo; I updated commit sha1. New commits:
ba31a5e  typo

comment:11 Changed 17 months ago by
 Reviewers set to Laith Rastanawi
 Status changed from needs_review to positive_review
comment:12 Changed 17 months ago by
 Branch changed from public/29127reb to ba31a5e505bb23ca2de502250bcc98352b66446b
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
implement `a_maximal_chain` for combinatorial polyhedron
implement `an_affine_basis` for polytopes
more description in the docs
used an_affine_basis to simplify is_inscribed
check sign of circumcenter using all vertices of simplex
apply change to 29125