Opened 19 months ago
Closed 19 months ago
#28464 closed defect (fixed)
.is_inscribed() makes a bad assumption in Polyhedron
Reported by: | jipilab | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.0 |
Component: | geometry | Keywords: | polytopes, |
Cc: | jipilab, gh-LaisRast, gh-kliem | Merged in: | |
Authors: | Thierry Monteil | Reviewers: | Jean-Philippe 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 follow-up: ↓ 2 Changed 19 months ago by
comment:2 in reply to: ↑ 1 Changed 19 months ago by
Replying to gh-LaisRast:
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 linear-time algorithm.
comment:3 Changed 19 months ago by
- Branch set to u/tmonteil/_is_inscribed___makes_a_bad_assumption_in_polyhedron
comment:4 Changed 19 months 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 19 months ago by
- Reviewers set to Jean-Philippe 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 19 months ago by
- Milestone changed from sage-8.9 to sage-9.0
moving milestone to 9.0 (after release of 8.9)
comment:7 Changed 19 months 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)