#29127 closed enhancement (fixed)

Implement an affine basis for polytopes

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.1
Component: geometry Keywords: polytopes, affine basis
Cc: jipilab, gh-LaisRast Merged in:
Authors: Jonathan Kliem Reviewers: Laith Rastanawi
Report Upstream: N/A Work issues:
Branch: ba31a5e (Commits, GitHub, GitLab) Commit: ba31a5e505bb23ca2de502250bcc98352b66446b
Dependencies: #29117 Stopgaps:

Status badges

Description (last modified by gh-kliem)

Sometimes it is useful to obtain dim + 1 vertices of a polytope in general position -- an affine basis.

With #29117, which provides a maximal chain of faces, we can easily obtain those vertices that are even guaranteed to be in general position for any realization of the polytope.

We apply this affine basis to simplify is_inscribed. This is also faster, as the current approach requires to compute all neighbors of a vertex (which can be pretty hard, even once this is done efficiently through combinatorial polyhedron):

Time without this ticket:

sage: P = polytopes.hypercube(8)
sage: %time P.is_inscribed()
CPU times: user 17.5 s, sys: 32.4 ms, total: 17.5 s
Wall time: 17.5 s
True

Time with this ticket:

sage: P = polytopes.hypercube(8)
sage: %time P.is_inscribed()
CPU times: user 17.5 ms, sys: 10 µs, total: 17.5 ms
Wall time: 17.4 ms
True

While we are at it, we fix a bug for the empty polyhedron, so that a_maximal_chain returns just a list of one empty face, instead of two.

Follow ups:

  • We use this to fix #29116.
  • We implement is_affinely_isomorphic.

Change History (12)

comment:1 Changed 18 months ago by gh-kliem

  • Description modified (diff)

comment:2 Changed 18 months ago by gh-kliem

  • Branch set to public/29127
  • Commit set to 231c16f3a948591183cf21bfff83226997201fea
  • Status changed from new to needs_review

New commits:

a8359e0implement `a_maximal_chain` for combinatorial polyhedron
6c4c1c0implement `an_affine_basis` for polytopes
3d87ccfmore description in the docs
1b78e87used an_affine_basis to simplify is_inscribed
5e547b3check sign of circumcenter using all vertices of simplex
231c16fapply change to 29125

comment:3 Changed 18 months ago by git

  • Commit changed from 231c16f3a948591183cf21bfff83226997201fea to 4fb0f6ba4cfd36da8f5f41a499c78aa82cccca4b

Branch pushed to git repo; I updated commit sha1. New commits:

4fb0f6bhandling small-dimensional cases

comment:4 Changed 18 months ago by gh-kliem

  • Branch changed from public/29127 to public/29127-reb
  • Commit changed from 4fb0f6ba4cfd36da8f5f41a499c78aa82cccca4b to d2d2a8a4ebc544f986cb38744eee91047371bca6

New commits:

61dd4a5implement `a_maximal_chain` for combinatorial polyhedron
a18011fimproved documentation
2e9f25fexposed a_maximal_chain to polyhedron_base
0315652implement `an_affine_basis` for polytopes
554556dmore description in the docs
aa30035used an_affine_basis to simplify is_inscribed
08b263eapply change to 29125
d2d2a8ahandling small-dimensional cases

comment:5 Changed 18 months ago by gh-kliem

  • Dependencies changed from #29117, #29125 to #29117

comment:6 Changed 17 months ago by gh-LaisRast

  • Status changed from needs_review to needs_work

Some typos

-        in the face lattices and picking for each cover relation
-        on vertex that is in the difference. Thus this method
+        in the face lattice and picking for each cover relationa
+        one vertex that is in the difference. Thus this method
        # We just in the folling that element in ``chain_indices`` is a sorted list
        # of V-indices.

Since you also implemented an_affine_basis for Polyhedron, maybe it is better to use it. Doing so, you can remove the following part of your code and thus making the code easier to read. I am saying this because if you use an_affine_basis for Polyhedron, you will have the whole polyhedron as a face.

        # Finally append some vertex not contained in ``face``,
        # which is a facet of ``self`` now.
        for i in range(len(face)):
            if face[i] != i:
                basis_indices.append(i)
                break
        else:  # no break
            basis_indices.append(len(face))
+}}}

comment:7 Changed 17 months ago by gh-kliem

  • Description modified (diff)

comment:8 Changed 17 months ago by git

  • Commit changed from d2d2a8a4ebc544f986cb38744eee91047371bca6 to b5f9be530140ad827cbdec2164103a44dc4caaf9

Branch pushed to git repo; I updated commit sha1. New commits:

5e0837ftypos
4606286bugfix in a_maximal_chain
b5f9be5simplify construction by using method in Polyhedron_base

comment:9 Changed 17 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:10 Changed 17 months ago by git

  • Commit changed from b5f9be530140ad827cbdec2164103a44dc4caaf9 to ba31a5e505bb23ca2de502250bcc98352b66446b

Branch pushed to git repo; I updated commit sha1. New commits:

ba31a5etypo

comment:11 Changed 17 months ago by gh-LaisRast

  • Reviewers set to Laith Rastanawi
  • Status changed from needs_review to positive_review

comment:12 Changed 17 months ago by vbraun

  • Branch changed from public/29127-reb to ba31a5e505bb23ca2de502250bcc98352b66446b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.