Recognizing Vertex

[v.shlyk]

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,

Vladimir Shlyk

[paffenholz]

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.

[v.shlyk]

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.