Opened 2 years ago

Closed 2 years ago

# `is_inscribed` depends on order of vertices

Reported by: Owned by: gh-kliem major sage-9.1 geometry polytopes, is inscribed jipilab, gh-LaisRast Jonathan Kliem Jean-Philippe Labbé N/A 3f9cc75 3f9cc75dfac02eb6b05ff49deabdfbd03b491f5f

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.

### comment:1 Changed 2 years ago by gh-kliem

• Description modified (diff)

### comment:2 Changed 2 years ago by gh-kliem

• Branch set to public/29125
• Commit set to 3f9cc75dfac02eb6b05ff49deabdfbd03b491f5f
• Status changed from new to needs_review

New commits:

 ​3f9cc75 `check sign of circumcenter using all vertices of simplex`

### comment:3 Changed 2 years ago by jipilab

• Reviewers set to Jean-Philippe Labbé
• Status changed from needs_review to positive_review

Looks good to me. Thanks for fixing this error!

Again, the pyflakes is fixed in another ticket.

### comment:4 Changed 2 years ago by vbraun

• Branch changed from public/29125 to 3f9cc75dfac02eb6b05ff49deabdfbd03b491f5f
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.