`is_inscribed` depends on order of vertices

kliem commented 4 years ago

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 commented 4 years ago

Description changed:

--- 
+++ 
@@ -8,6 +8,7 @@
 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_(

kliem commented 4 years ago

Branch: public/29125

kliem commented 4 years ago

New commits:

3f9cc75 check sign of circumcenter using all vertices of simplex

kliem commented 4 years ago

Commit: 3f9cc75