The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [polytope]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
9
votes
0answers
119 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 ...
2
votes
1answer
137 views

Finding whether $n$ polytopes have nontrivial intersection from pairwise comparisons

I have a set of $n$ convex polytopes of the form $$\mathcal{L_i} = \{ \beta \mid C_i \beta \leq 0 \}$$ where $C$ is a matrix and $\beta$ is a vector. I know that for each pair of polytopes $$(\...
5
votes
1answer
129 views

Complexity of Finding Largest Set of Intersecting Convex Polytopes

I have a set of $n$ convex polytopes, and I wish to find the largest subset of those polytopes that shares at least one point in common. I think that this problem should be NP-hard, but I am ...
0
votes
0answers
8 views

Extension complexity of convex hull of vertex intersection of nicely behaved polytopes?

Take two convex bounded polytopes $P_1$ and $P_2$ where a. $P_2\subseteq P_1$ b. $\mathcal{V}(P_1)\cap\mathcal{V}(P_2)\neq\emptyset$ where $\mathcal{V}(P_i)$ is vertex set of $P_i$ at $i\in\{1,2\}$. ...
0
votes
0answers
26 views

Does simplex algorithm work in this case?

Essentially I want to know if we have two polytopes $P_1$ and $P_2$ in $\mathbb R^n$ and we maximize on $P_1\cap P_2$ where a. $P_2\subseteq P_1$ b. $\mathcal{V}(P_2)\cap\mathcal{V}(P_1)\neq\...
13
votes
1answer
510 views

Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

I have a polytope $P$ defined by $\{ x : Ax \leq b, x \geq 0\}$ . Question: Given a vertex $v$ of $P$, is there a polynomial time algorithm to uniformly sample from the neighbors of $v$ in the graph ...
5
votes
1answer
226 views

Reaching the double exponential upper bound in Fourier-Motzkin elimination

One round of Fourier-Motzkin elimination may yield $n^2/4$ inequalities where $n$ is the original number of linear inequalities, whence an upper bound of $n^{2^d}/2^{2^{d+1}-2}$ for $d$ rounds of ...
0
votes
1answer
123 views

On polytope lattice points

Given a convex polytope let the width of the polytope be $d$ and the farthest euclidean distance between any points in the polytope be $e$. Denote $\mathcal P(a,c)$ to be the set of convex polytopes ...
9
votes
0answers
96 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 ...
4
votes
1answer
65 views

Reference needed for lower bound on number of guards in three-dimensional art gallery guarding

During my research (writing my master's thesis) I've stumbled across the book Art Gallery Theorems and Algorithms by O’Rourke. In chapter 10 (pdf available on the above site), section 10.2.2. he shows ...
1
vote
1answer
91 views

Properties of convex polytope of 0-1 matrices

Problem setting Consider a set $ S = \big\{ 1,2,\cdots,n \big\}$. Now consider $k$ equal-sized subsets $S_i \subset S$ s.t of size $\big|S_i\big|=n' \;\forall i$. Consider a $k\times k$ matrix $M$ ...
10
votes
0answers
123 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 ...
3
votes
0answers
100 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 ...
6
votes
1answer
286 views

Decide whether a point is a vertex of a polytope?

Inspired by the question, I would like to ask the following question: Input: A polytope specified by $\Theta=\{\vec{x}\mid A\vec{x}\leq b\}$, and its affine projection $f(\Theta)= \{(\vec{c}_1\cdot \...
2
votes
0answers
70 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 ...
14
votes
2answers
955 views

Checking equivalence of two polytopes

Consider a vector of variables $\vec{x}$, and a set of linear constraints specified by $A\vec{x}\leq b$. Furthermore, consider two polytopes $$\begin{align*} P_1&=\{(f_1(\vec{x}), \cdots, f_m(\...
-1
votes
1answer
275 views

Vertices of a polytope

Consider the polytope $P=\{(x_1,x_2,...,x_n)\in \mathbb{R}^n| \sum_{i=1}^n x_i=1; 0\leq a_i\leq x_i\leq b_i, i=1,...,n\}$ where $a_i$ and $b_i$ are constant lower and upper bounds for $x_i$. Is it ...
4
votes
1answer
185 views

When are all facets rank facets? (for independence system polyhedra)

Consider an independence system $(E,\mathcal{I})$, and the corresponding polytope: $P(E,\mathcal{I}):=\operatorname{conv.hull}\{ x^S ~|~S\in \mathcal{I}\}$ where $x^S \in \{0,1\}^E$ denotes the ...
8
votes
1answer
435 views

Is the feasible region of this SDP polyhedral?

We have a semidefinite program (SDP) whose feasible region contains only a finite number of rank-$1$ matrices. Can we conclude that the feasible region of this SDP is polyhedral? We believe this to ...
5
votes
0answers
142 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?
2
votes
3answers
249 views

The number of integral points in a polytope

Suppose we define a polytope with $$ \mathbf{Ax} \leq \mathbf{b} $$ What is the best way to find/approximate the number of the integral points in the polytope? Update: how hard is the complexity ...
0
votes
0answers
133 views

An interesting class of colored graphs?

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 ...
3
votes
1answer
186 views

What is known about this binary representation polytope?

Consider the following set. $S_n =\{ (x,y) ~|~x \in \mathbb{Z}_+~\wedge~ y \in \{0,1\}^n ~\wedge~x=\sum_{i=0}^{n-1} 2^i y_i \}$ $S_n$ is a collection of pairs $(x,y)$, where $x$ is an integer ...