Opened 2 years ago

Closed 2 years ago

#29125 closed defect (fixed)

`is_inscribed` depends on order of vertices

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.1
Component: geometry Keywords: polytopes, is inscribed
Cc: jipilab, gh-LaisRast Merged in:
Authors: Jonathan Kliem Reviewers: Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: 3f9cc75 (Commits, GitHub, GitLab) Commit: 3f9cc75dfac02eb6b05ff49deabdfbd03b491f5f
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-kliem)

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()
sage: P = Polyhedron(vertices=[[-2,-1], [-2,1], [0,-1], [0,1]], backend='field')
sage: P.is_inscribed()
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.

Change History (4)

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:

3f9cc75check 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.