# How to check whether two points belong to same facet of polyhedron

I have a (convex) polyhedron $P \in \mathbb{R}^n$, defined by a set of linear inequalities. $P$ can be degenerate i.e. some of the inequalities can actually imply some equality. I have two points $x,y \in \mathbb{R}^n$ such that $x,y \in P$. How to check whether $x$ and $y$ belong to same facet ( or face) or not ? Can we do this computationally ?

I can assume $x,y$ to be extreme points of $P$, if that helps.

I have an approach but I don't know whether it will always work. Let the inequalities be defined as $a_i x \leq b_i$ for $i=1,2,\ldots,k$ where $a_i \in \mathbb{R}^n$ and $b_i \in \mathbb{R}$. We can check for all inequalites by putting x and y in them. i.e. if $a_i x=a_i y=b_i$ then the belong to same facet. Is there any issue with this approach.

• Can you give an example of set of inequalities ? – stity Nov 28 '17 at 11:05
• Any finite number of linear inequalities like $a_i x \leq b_i$ for $i=\{1,2,\ldots k\}$ where $a_i \in \mathbb{R}^n$ and $b_i \in \mathbb{R}$. I edited the question to linear inequalities. – user402940 Nov 28 '17 at 11:07
• I guess you'll have to classify your inequalities to "degenerate", i.e. those which turn into equalities for the whole relint(P), and the rest. – Ivan Neretin Nov 28 '17 at 11:20
• Yeah. I meant it may be degenerate. I forgot to frame the question in that sense. Edited now. – user402940 Nov 28 '17 at 11:23
• As you said, if $a_ix=a_iy=b_i$ then $x$ and $y$ belong to the same hyperplane. As your polyhedron is convex (finite intersection of convex sets), your points belong to the same facet – stity Nov 28 '17 at 12:28