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.

  • $\begingroup$ Can you give an example of set of inequalities ? $\endgroup$ – stity Nov 28 '17 at 11:05
  • $\begingroup$ 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. $\endgroup$ – user402940 Nov 28 '17 at 11:07
  • $\begingroup$ 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. $\endgroup$ – Ivan Neretin Nov 28 '17 at 11:20
  • $\begingroup$ Yeah. I meant it may be degenerate. I forgot to frame the question in that sense. Edited now. $\endgroup$ – user402940 Nov 28 '17 at 11:23
  • $\begingroup$ 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 $\endgroup$ – stity Nov 28 '17 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.