Computational Complexity of VERTICES_IN_FACETS

[joswig]

Here is a question that I received:

I was wondering what computational complexity I can expect from
VERTICES_IN_FACETS for m vertices on the d sphere. Does it rely on a convex
hull algorithm? If yes, on which? As I am using this wonderfully
practicable function as a non-specialist in convex geometry, I apologize if
this is a naive question.

[joswig]

Indeed, polymake employs a convex hull computation to compute the vertex-facet incidences from input points. Most algorithms/implementations produce FACETS and VERTICES_IN_FACETS together. If this is not the case there is a second step to compute scalar products between each row of VERTICES and each row of FACETS to obtain those incidences; this is negligible.

polymake supports many convex hull codes; the default is PPL, which implements double description (= Fourier-Motzkin elimination). For (many more) details see our user guide and experiments associated with this paper.

In general, it is next to impossible to say which algorithm works best (the above mentioned paper gives 10 rules of thumb; that's the best what we have). If your points are known to lie on the sphere I would try beneath-and-beyond, which is polymake's native convex hull algorithm. For points uniformly sampled at random on the sphere that algorithm runs in expected linear time in the number of points, in fixed dimension. For points in general position (not necessarily on the sphere) reverse search has running time O(mnd) if d=dimension, m=number of facets and n=number of vertices.

If you consider the dimension as part of the input, then all known algorithms are worst case exponential (measured in the combined size of the input and the input).

[DanDan]

Thanks a lot for the answer.

Ok, so for fixed dimension d, assuming the resulting polytope to be simplicial (with prob 1) is indeed crucial for the algorithms to run in linear time? Otherwise, we do have to stick with the general case of exponential time?
May I ask to suggest a paper that I can refer to when I want to say: there is a linear time algorithm that gives me the vertex-facet incidence matrix (or computes the convex hull) for points in general position on the d-sphere? (as far as I could see, this is not contained in the paper referenced above?)

Best,
Daniel

[joswig]

OK, so for fixed dimension d, assuming the resulting polytope to be simplicial (with prob 1) is indeed crucial for the algorithms to run in linear time?

This is not what I said. Note that in the expression O(mnd) the parameter m (number of facets) depends on n (number of vertices/input points). Roughly speaking, m lies in \Theta(n^(d/2)) by the upper bound theorem. The complexity O(mnd) is attained, e.g., by reverse search of Avis and Fukuda (1991).

In fixed dimension and for points on the unit sphere, m is bounded by a linear function in n (see Borgwardt 1987).

At any rate, computing the vertex facet incidences takes O(mnd) time (by checking mn scalar products in R^d, if both the vertices and the facets are known; no other conditions on the polytope), and there is no way to make this faster.

All complexity statements refer to the unit cost model.