Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

is_inscribed depends on order of vertices #29125

Closed
kliem opened this issue Jan 31, 2020 · 7 comments
Closed

is_inscribed depends on order of vertices #29125

kliem opened this issue Jan 31, 2020 · 7 comments

Comments

@kliem
Copy link
Contributor

kliem commented Jan 31, 2020

Currently the inscription test for polyhedra depends on the order of vertices:

sage: Polyhedron(vertices=[[-2,-1], [-2,1], [0,-1], [0,1]]).is_inscribed()
True
sage: P = Polyhedron(vertices=[[-2,-1], [-2,1], [0,-1], [0,1]], backend='field')
sage: P.is_inscribed()
False
sage: V = P.Vrepresentation()
sage: H = P.Hrepresentation()
sage: parent = P.parent()
sage: dic = {True: 0, False: 0}
sage: for V1 in Permutations(V):
....:     P1 = parent._element_constructor_(
....:         [V1, [], []], [H, []], Vrep_minimal=True, Hrep_minimal=True)
....:     dic[P1.is_inscribed()] += 1
....:     
sage: dic
{True: 18, False: 6}

The algorithm constructs a sphere around dim + 1 vertices in general position. The circumcenter is computed up to sign. Then, one vertex is taken to determine, which sign to choose. However, up to dim vertices might lie on the intersection of both spheres.

We fix this by checking distance from the circumcenter for all vertices of that simplex.

CC: @jplab @LaisRast

Component: geometry

Keywords: polytopes, is inscribed

Author: Jonathan Kliem

Branch/Commit: 3f9cc75

Reviewer: Jean-Philippe Labbé

Issue created by migration from https://trac.sagemath.org/ticket/29125

@kliem kliem added this to the sage-9.1 milestone Jan 31, 2020
@kliem

This comment has been minimized.

@kliem
Copy link
Contributor Author

kliem commented Jan 31, 2020

Branch: public/29125

@kliem
Copy link
Contributor Author

kliem commented Jan 31, 2020

New commits:

3f9cc75check sign of circumcenter using all vertices of simplex

@kliem
Copy link
Contributor Author

kliem commented Jan 31, 2020

Commit: 3f9cc75

@jplab
Copy link

jplab commented Feb 7, 2020

Reviewer: Jean-Philippe Labbé

@jplab
Copy link

jplab commented Feb 7, 2020

comment:3

Looks good to me. Thanks for fixing this error!

Again, the pyflakes is fixed in another ticket.

@vbraun
Copy link
Member

vbraun commented Feb 11, 2020

Changed branch from public/29125 to 3f9cc75

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants