<p>I was wondering if anybody had any pointers to:</p>

<pre><code> 1. References for the problem of vertex counting on convex polytopes
 2. Possible implementations of known algorithms for such problem
</code></pre>

<p>So far I found:</p>

<ul>
<li><a href="http://www.ifor.math.ethz.ch/~fukuda/cdd_home/index.html" rel="nofollow">cdd</a> (by <a href="http://www.ifor.math.ethz.ch/~fukuda/" rel="nofollow">Komei Fukuda</a>)</li>
<li><a href="http://cgm.cs.mcgill.ca/~avis/C/lrs.html" rel="nofollow">lrs</a> (by <a href="http://cgm.cs.mcgill.ca/~avis/" rel="nofollow">David Avis</a>)</li>
<li><a href="http://www.mpi-inf.mpg.de/~behle/azove.html" rel="nofollow">azove</a> (by <a href="http://www.mpi-inf.mpg.de/~behle/index.html" rel="nofollow">Markus Behle</a>)</li>
</ul>

<p>The references to the corresponding methods can be found on the authors websites and the corresponding documentation.</p>

<p>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}$.</p>

<h3>A second question motivated by the last method:</h3>

<p>Assuming that it's possible, are there any known methods for computing a <a href="http://www.math.tu-bs.de/~pfetsch/apropo/HTML3/Isomorphism.html" rel="nofollow">combinatorially isomorphic</a> polytope $A$ with coefficients in $\mathbb{R}$ from a polytope $A$ with coefficients in $\mathbb{Z}$? </p>

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

<h3>A third related question:</h3>

<p>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}$?</p>

CC BY-SA 3.0
2011-09-07T01:35:32.893Z
(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. :)
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-07T02:19:45.300Z
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.
Amelio Vazquez-Reina
CC BY-SA 3.0
2011-09-07T02:21:24.523Z
As I wrote, I do not know whether “a polytope in the general case” includes non-convex ones or the high-dimensional ones (that is, dimension is greater than 3) or both.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-07T02:23:11.330Z
Thanks @Tsuyoshi I was just updating my comment. I am interested in convex polytopes, I'll update the OP.
Amelio Vazquez-Reina
CC BY-SA 3.0
2011-09-07T02:26:27.953Z
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](http://dx.doi.org/10.1007/BF02985377) and the references in it.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-07T15:04:18.290Z
Thanks @Tsuyoshi Ito. I'll update the OP with your answer.
Amelio Vazquez-Reina
CC BY-SA 3.0
2011-09-07T19:54:55.300Z
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](http://www.ifor.math.ethz.ch/teaching/lectures/poly_comp_ss11/lecture4) (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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-07T21:28:00.987Z
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](http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme)
Amelio Vazquez-Reina
<co.combinatorics><counting-complexity><software>
Vertex counting on convex polytopes
Amelio Vazquez-Reina
# Vertex counting on convex polytopes

(Asked by: username_0 on 2011-09-06)

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:

cdd (by Komei Fukuda)
lrs (by David Avis)
azove (by Markus Behle)

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 username_1'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}$?

**Tags:** co.combinatorics, counting-complexity, software

> **Comments:**
> **username_1**: (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. :)  
> **username_0**: 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.  
> **username_1**: As I wrote, I do not know whether “a polytope in the general case” includes non-convex ones or the high-dimensional ones (that is, dimension is greater than 3) or both.  
> **username_0**: Thanks @Tsuyoshi I was just updating my comment. I am interested in convex polytopes, I'll update the OP.  
> **username_1**: 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](http://dx.doi.org/10.1007/BF02985377) and the references in it.  
> **username_0**: Thanks @username_1. I'll update the OP with your answer.  
> **username_1**: 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](http://www.ifor.math.ethz.ch/teaching/lectures/poly_comp_ss11/lecture4) (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.  
> **username_0**: 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](http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme)  

---

## 0 answers

