Page 1 of 1

### Recognizing Vertex

Posted: 22 May 2011, 22:52
Dear Polymake people,

Can anybody say anything useful regarding the following question?

Let P be an integer polyhedron (in particular polytope) in R^n. So, all its vertices are integer points.
Asume also that we don’t know the facets of P and even the inequalities defining P explicitly; as is in the case when P is defined as the convex hull of some set of points.

Consider the problem: ‘Is a given integer point \$t\$ in P a vertex of P?’ (1)
(1) is equivalent to:
‘Is it true that \$t\$ is not a convex combination of any \$k\geq 2\$ points in P?’, (2)
which is hardly useful to solve (1).

(2) can be reformulated in the combinatorial language for \$k=2\$.
The question is:
Can you reformulate (2) in any fruitful way for \$k=3,\$ \$k=4,\$ … or in the general case?

I don’t think that using the hyperplanes separating \$t\$ from other points in P
or the facets passing through \$t\$ is a good idea. Is this right?

Any reference to a special polyhedron, for which this has been done would be favorably accepted.

Thank you,

### Re: Recognizing Vertex

Posted: 23 May 2011, 00:13
I am not sure whether I completely understand your question. You are given a set of points M, and you want to determine the vertices of P:=conv(M), so you want to decide for each m in M whether m is a vertex of P?

Deciding whether m is contained in the convex hull of some points could be phrased as a linear programming problem. See e.g. here for some background. polymake has, via cdd or lrs, methods for redundancy removal that are more efficient than convex hull computation.

Maybe a better place to ask such a general question would be mathoverflow, as that forum has a substantially larger community.

### Re: Recognizing Vertex

Posted: 25 May 2011, 01:29
Yes, you understand the question right. But I have exp(d) points in R^d (at the moment, 2500 points for d=50; 61000 points for d=100). So, I would like to escape solving LP programs so many times. However, I know allready that all my points cannot be expressed as a convex combination of 2 other points. And I also know (or expect) that only a few of them can be expressed via 3 points and even more less via 4 and so on. That is why I am asking about any combinatorial or any other characteristic property to determine whether a given point is a convex combination of some 3,4,... points. The problem in the general setting looks hard but it is quite possible that for the case of 3 points such property could exist. Even if being hard to verify it could be useful to rise higher in \$d\$.

Thank you for informing me about mathoverflow.