3
$\begingroup$

I was wondering if anybody had any pointers to:

 1. References for the problem of vertex counting on convex polytopes
 2. Possible implementations of known algorithms for such problem

So far I found:

The references to the corresponding methods can be found on the authors websites and the corresponding documentation.

The first two focus more on vertex enumeration and not just counting, while the third one focuses on the problem of counting 0/1 vertices on polytopes with coefficients in $\mathbb{Z}$.

A second question motivated by the last method:

Assuming that it's possible, are there any known methods for computing a combinatorially isomorphic polytope $A$ with coefficients in $\mathbb{R}$ from a polytope $A$ with coefficients in $\mathbb{Z}$?

Update: The answer to this last question seems to be no (see Tsuyoshi Ito's comment below)

A third related question:

Not sure if the answer to the previous question answers this one, but are there any known transformations that preserve vertex cardinality from polytopes with coefficients in $\mathbb{R}$ to polytopes with coefficients in $\mathbb{Z}$?

Improve this question
$\endgroup$
8
  • $\begingroup$ (1) What do you mean by “general polytopes”? Namely, are they convex, and what is their dimension (3 or general)? (2) The second question must contain some typo; otherwise I am sure that the identity mapping will do the job. :) $\endgroup$ – Tsuyoshi Ito Sep 7 '11 at 1:35
  • $\begingroup$ Thanks @Tsuyoshi. I fixed the typo :). As for general polytopes vs other polytopes, my understanding is that some counting methods are restricted to non-degenerate polytopes or to 0/1 polytopes (i.e. those with 0/1 vertices), and I am interested in the counting problem in the general case. I'm happy to clarify this in the OP further. $\endgroup$ – Amelio Vazquez-Reina Sep 7 '11 at 2:19
  • 3
    $\begingroup$ It is not always possible to convert a (convex) polytope to a combinatorially isomorphic one with rational coordinates, when the dimension is higher than three. See Ziegler 2008 and the references in it. $\endgroup$ – Tsuyoshi Ito Sep 7 '11 at 2:26
  • 2
    $\begingroup$ I do not know if you are aware of this or not, but it is known that counting vertices of a polytope (given as a system of linear inequalities) is #P-hard. See e.g. the lecture notes by Komei Fukuda (under the heading “Bipartite case”). This means that there is no polynomial-time algorithm which answers the number of vertices of a given polytope unless P=NP (more precisely, unless P=PP). The hardness holds even when the polytope is promised to be a 0/1-polytope. $\endgroup$ – Tsuyoshi Ito Sep 7 '11 at 19:54
  • 1
    $\begingroup$ Thanks @Tsuyoshi, I knew the general case was #P-hard, but did not know it extended to the 0/1 case as well. I guess what I am wondering if there are any other state-of-the-art methods besides those I listed, and if there has been any progress on this matter, maybe along the lines of PTAS or PRAS $\endgroup$ – Amelio Vazquez-Reina Sep 7 '11 at 21: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.