All Questions
10 questions
4
votes
1
answer
3k
views
Find the minimum distance between two convex hulls
We work over $\mathbb{R}^N$. Let $\mathbf{P}_1$ denote the hyperplane constructed using $N$ points, each of which is on a different axis (there are $N$ axes). We denote by $\mathbf{P}_2$ the convex ...
- 233
4
votes
0
answers
46
views
Implementation of Friedman's algorithm of reconstructing simple polytopes
In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...
3
votes
1
answer
152
views
A question about polytopes related to linear programming
Given linear functions $f_1({\bf x}),\dots,f_n({\bf x})$ on ${\bf R}^m$, let $K = \{(a_1,\dots,a_n) \in {\bf R}^n:$ the $n$ halfspaces $\{{\bf x}: f_i({\bf x}) \leq a_i\} $ have nonempty intersection$\...
- 19.7k
2
votes
0
answers
210
views
Finding optimal linear transformation for intersection of convex polytopes
I previously posted this on MathSE and am now trying here.
I have the following situation, as shown in the following diagram:
$W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in blue) ...
- 695
1
vote
1
answer
391
views
Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces
Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by
$$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$
$$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$
I wish to find their convex hull, that is a ...
- 2,689
1
vote
1
answer
1k
views
Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]
Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...
- 11
1
vote
0
answers
36
views
Does Hoffman constant keep the same after a very tiny perturbation on the polyhedron such that the bases are even unchanegd?
Suppose that $P$ is a polyhedron represented by
$$P:=\{x \in \mathbb{R}^n: A x \le b \} \text{ for }A \in \mathbb{R}^{m\times n},\ b \in \mathbb{R}^m,$$
and $P$ contains interior points. Moreover, the ...
- 33
0
votes
0
answers
165
views
Minimum circumscribed ellipsoid of $\mathcal H$-polytope
Given matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^n$, consider the $\mathcal H$-polytope $P$ defined as follows
$$ P := \left\{ x \in \mathbb{R}^n : Ax \leq b \right\} $$
I ...
- 235
0
votes
0
answers
93
views
Number of vertices in a polyhedron
Consider polytopes
$$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$
$$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$
$$B[z_{1},z_{2},z]'\leq c$$
having vertex count $v_1,v_2$ and $v$ respectively.
We ...
- 13.9k
0
votes
0
answers
369
views
Finding a point in the relative interior of the convex hull of a set of integer-valued vectors
Let $X \subset \mathbb{Z}^n$ be the set of integer-valued vectors satisfying a system of linear constraints. We can suppose that $X$ is the set of integral points in a given polyhydral set $Y \subset \...
- 136