0

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.

user402940
  • 381
  • 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
  • Thanks. I think your reasoning implies my approach is correct. – user402940 Nov 28 '17 at 12:34
  • @user402940 that's what I meant indeed – stity Nov 28 '17 at 13:07

0 Answers0