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

Hi there,

I have two questions and I wonder if any of you may know the answer.

1 What algorithm does sage use to test whether a given point is in a polyhedron, namely in the function polyhedron.contains()?

1. Is there a difference in the algorithm according to whether the V-polyhedron is a V-polytope or is unbounded?

Thank you, and best regards, Guillermo

edit retag close merge delete

This may depend on the backend used, so can you give an example of a Polyhedron for which you want to know the answer?

( 2019-10-22 07:06:00 -0500 )edit

Sort by » oldest newest most voted

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

more