About algorithm for testing whether a point is in a V-polyhedron

savecancel

You can access the algorithm for containment by doing the following:

sage: p = polytopes.cube()
sage: p.contains??

This will show you the source code for this function. The containment check is independent of the backend. Currently, when you create a polyhedron object in Sage, it computes the other representation (H- to V-, or V- to H-) automatically (this may change in the future, but for now, it is so). Then, checking containment is obtained directly from the H-representation by matrix multiplication and checking the equality or inequality of Ax<=B. This is then done in the arithmetic of the appropriate ring (ZZ, QQ, RDF, NumberField, etc).

There is absolutely no difference between bounded vs unbounded polyhedron.

To know if the function depends on the backend, you can look next to the 1-to-last line in the output of p.contains?? it will mention the file in which this function is. If this file contains ppl, normaliz, polymake, cdd, field, then this function is implemented specifically for that backend. Otherwise, if it is in say base.py, it is a generic function that is used in general...