# Questions tagged [polytope]

The tag has no usage guidance.

8 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
152 views

### Is counting the total number of faces of a polytope $\#P$ hard?

Let $P$ be a polytope defined by $Ax = b, x \geq 0$. Question: What is the complexity of computing the total number of faces of $P$? I know counting vertices is $\# P$-complete, but this problem is ...
144 views

### Which convex polytopes have volumes of polynomial bit-length?

A convex polytope is described as an intersection of halfspaces, given as inequalities between linear combinations of variables with rational coefficients. The volume computation problem for convex ...
118 views

### Complexity of checking the equivalence of constraints and generator descriptions of convex polyhedra

Consider the space $\mathbb{Q}^n$. A convex polyhedron is defined, equivalently, by a system of linear (in)equalities (with integer coefficients) or by a system of generators: vertices, and in case ...
146 views

### Computing diameter of a 3D polyhedron

A polyhedron is given as a set of its vertex coordinates. Is it possible to find its diameter faster than $O(n^2)$? Or, maybe, some another common polyhedron representation would help fasten this?
112 views

### Equivalence of weighted Minkowski sums

Given $n$ polytopes $P_1, \cdots, P_n$, each $P_i$ is given as the V-representation, i.e., a set of $m$ points as its set of vertices. Furthermore, consider a variant of the Minkowski sum (somehow ...
71 views

### Check whether a point is a vertex of Minkowski sum of polytopes

Given $n$ polytopes \begin{align*} P_1&=\{(f^1_1(\vec{x}_1), \cdots, f^1_m(\vec{x}_1))\mid A_1\vec{x}_1\leq b_1\}\\ P_2&=\{(f^2_1(\vec{x}_2), \cdots, f^2_m(\vec{x}_2))\mid A_2\vec{x}_2\leq ...
Let $G$ be a complete graph edge-colored with $k$ colors. We say that $G$ is Gallai-colored if no triangle is colored with three distinct colors. Fix a tuple of integers $c = (c_1,\ldots,c_k)$. We may ...