Ask Your Question
2

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

asked 2019-10-22 04:42:20 -0500

guillermo gravatar image

updated 2020-06-01 07:46:13 -0500

FrédéricC gravatar image

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 flag offensive close merge delete

Comments

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

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

1 answer

Sort by » oldest newest most voted
1

answered 2019-10-25 13:12:07 -0500

jipilab gravatar image

updated 2019-10-25 16:50:46 -0500

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

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2019-10-22 04:42:20 -0500

Seen: 45 times

Last updated: Oct 25 '19