Opened 3 years ago
Closed 3 years ago
#28464 closed defect (fixed)
.is_inscribed() makes a bad assumption in Polyhedron
Reported by:  jipilab  Owned by:  

Priority:  major  Milestone:  sage9.0 
Component:  geometry  Keywords:  polytopes, 
Cc:  jipilab, ghLaisRast, ghkliem  Merged in:  
Authors:  Thierry Monteil  Reviewers:  JeanPhilippe Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  12a15b8 (Commits, GitHub, GitLab)  Commit:  12a15b80421aae50e85555cdc346034d803c01d8 
Dependencies:  Stopgaps: 
Description
There is an error in the code for is_inscribed
, where one assume that any d
neighbors of a vertex necessarily span the space. This is wrong.
The following (most likely not minimal example) reproduces this:
sage: P = Polyhedron(vertices=[(130658298093891402635075/416049251842505144482473, ....: 177469511761879509172000/1248147755527515433447419, ....: 485550543257132133136169/2496295511055030866894838, ....: 2010744967797898733758669/2496295511055030866894838), ....: (146945725603929909850/706333405676769433081, ....: 84939725782618445000/706333405676769433081, ....: 560600045283000988081/1412666811353538866162, ....: 969778382942371268081/1412666811353538866162), ....: (46275018824497300/140422338198040641, ....: 5747688262110000/46807446066013547, 1939357556329/7033601552658, ....: 1939357556329/7033601552658), (17300/59929, 10000/59929, 39929/119858, ....: 39929/119858), (4700/32209, 10000/32209, 12209/64418, 12209/64418), ....: (QQ(0), QQ(0), QQ(0), QQ(1)), (QQ(0), QQ(0), 1/2, 1/2), (300/10027, ....: 10000/30081, 10081/60162, 10081/60162), (112393975400/1900567733649, ....: 117311600000/633522577883, 43678681/95197362, 43678681/95197362), ....: (6109749955400/133380598418321, 37106807920000/133380598418321, ....: 2677964249/6680888498, 2677964249/6680888498), ....: (29197890764005600/402876806828660641, ....: 2150510776960000/402876806828660641, ....: 398575785274740641/805753613657321282, ....: 398575785274740641/805753613657321282), ....: (5576946899441759759983005325/110078073300232813237456943251, ....: 29071211718677797926570478000/110078073300232813237456943251, ....: 59439312069347378584317232001/220156146600465626474913886502, ....: 181346577228466312205473034501/220156146600465626474913886502), ....: (150040732779124914266530235300/6774574358246204311268446913881, ....: 2813827375989039189507000218000/6774574358246204311268446913881, ....: 1260217414021285074925933133881/13549148716492408622536893827762, ....: 3232518047094242684574253773881/13549148716492408622536893827762), ....: (3816349407976279597850158016285000/88842127448735433741180809504357161, ....: 27965821247423216557301387453968000/88842127448735433741180809504357161, ....: 68546256000224819256028677086357161/177684254897470867482361619008714322, ....: 86062257922545755787315412690197161/177684254897470867482361619008714322)]) sage: P.is_inscribed() Traceback (most recent call last): ... ZeroDivisionError: rational division by zero
The matrix a
has zero determinant and causes this error. One should pick the neighbors more carefully to fix this.
Change History (7)
comment:1 followup: ↓ 2 Changed 3 years ago by
comment:2 in reply to: ↑ 1 Changed 3 years ago by
Replying to ghLaisRast:
This is indeed overkill: a set of vectors form a matroid, so you can select a maximal independent set of vectors greedily, leading to a lineartime algorithm.
comment:3 Changed 3 years ago by
 Branch set to u/tmonteil/_is_inscribed___makes_a_bad_assumption_in_polyhedron
comment:4 Changed 3 years ago by
 Commit set to 12a15b80421aae50e85555cdc346034d803c01d8
 Status changed from new to needs_review
New commits:
12a15b8  #28464 : fix the construction of a simplex of vertices in Polyhedron_base.is_inscribed

comment:5 Changed 3 years ago by
 Reviewers set to JeanPhilippe Labbé
 Status changed from needs_review to positive_review
Salut,
Looks good to me! I also like the second example, which is simpler. I was thinking about trying to reproduce the error with a smaller one, but then it all depends on the internal order given to vertices... But it is good in any case to have that one too.
I set this to positive review. Error fixed!
Merci pour la réparation rapide!
comment:6 Changed 3 years ago by
 Milestone changed from sage8.9 to sage9.0
moving milestone to 9.0 (after release of 8.9)
comment:7 Changed 3 years ago by
 Branch changed from u/tmonteil/_is_inscribed___makes_a_bad_assumption_in_polyhedron to 12a15b80421aae50e85555cdc346034d803c01d8
 Resolution set to fixed
 Status changed from positive_review to closed
With out getting deeply into the algorithm, a naive solution to this problem is to iterate over all possible subsets (of size
dimension
) ofvertex_neighbors
, and test if the resulting polytope (convex hull ofvertex
and that subset of neighbors) is a simplex. But this however can be costly.Just because I was testing it, this is what I believe the smallest example where the current implementation of the method
is_inscribed()
fails. This is a pyramid over a pyramid over a square (with a specific ordering of the vertices)