Questions tagged [convex-geometry]
The convex-geometry tag has no usage guidance.
14
questions with no upvoted or accepted answers
11
votes
0
answers
199
views
On preprocessing a convex polyhedron prior to sampling
Most of the algorithms for estimating the volume of a convex polyhedron $K \subset R^d$ assume the existence of an affine transform $T$ with the property that
$$ B \subset TK \tilde{\subset}\ \...
- 31.9k
10
votes
0
answers
150
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 ...
- 8,234
10
votes
0
answers
295
views
Approximating a convex polyhedron, with fewer inequalities
I have a convex polyhedron $\mathcal{P}$, given by $n$ linear inequalities $a_i \cdot x \le c_i$ where $x$ is a $d$-dimensional vector over the non-negative real numbers. In other words,
$$\mathcal{...
- 11.3k
6
votes
0
answers
347
views
Approximating the diameter of a convex set defined by semidefinite constraints
A convex subset $C$ of $\mathbb{R}^{n^2}$ is given as the set of positive semidefinite $n\times n$ matrices whose coefficients fulfill some affine equations.
Now, if you want to minimize a linear ...
5
votes
0
answers
259
views
Intersection of Hamming Balls
I am interested in the volume of the intersection of two Hamming balls of radius say m/6 in m-dimensional space, the distance between whose centers is about \sqrt{m}. I would ideally like this to be a ...
- 51
3
votes
0
answers
123
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 ...
- 89
3
votes
0
answers
187
views
Computing the convex hull of several polyhedra
Let $K_1,..., K_m$ be a set of $m$ polyhedra, with $K_i\subseteq \mathbf{R}^n$, for all $i\in [m]$, and each is described by a set of $poly(n)$ linear inequalities.
How easy is it to compute an ...
- 1,224
2
votes
0
answers
148
views
Is the following problem in $coNP$?
Given an $n\times n$ matrix $M$ with $\mathbb Z$ entries is 'does an $\frac n2\times\frac n2$ minor of $M$ vanish?' in $\bf{coNP}$?
At least one $\frac n2\times\frac n2$ minor non-vanish implies rank ...
- 12.6k
1
vote
0
answers
69
views
How can we prove what the shortest line between two points avoiding convex obstacles is? (visibility graphs)?
I came across the observation in russell & norvig's artificial intelligence book that the shortest path between two points while avoiding convex polygonal obstacles is a sequence of line segments ...
- 119
1
vote
0
answers
14
views
Size of solutions in integer programming
Given a linear integer program $Ax\leq b$ with $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ known is there a polynomial time algorithm to give tight upper bounds for $\log_2\|x\|_\infty$ and $\...
- 12.6k
1
vote
0
answers
130
views
Hausdorff Distance and Convex Hull
Given two sets of points A and B, both in $R^d$, is there a relation between the convex hulls of A and B, i.e. conv(A) and conv(B), w.r.t. the Hausdorff distance between A and B? In other words, does ...
- 209
1
vote
0
answers
85
views
Compute basis of vertex set of polytope
I am wondering whether there is an efficient algorithm to compute the basis of the set of vertices of a polytope.
Formally,
INPUT: a polytope
$$\Xi=\{(\vec{a}_1\vec{x}+\vec{b}_1, \cdots, \vec{a}_m\...
- 89
1
vote
0
answers
135
views
Orlicz Norm and a result on expectation
I am reading a paper which is mainly about Dobrushin's contraction coefficient and its generalization. In page 27, the following is defined:
Consider an arbitrary, non-negative, convex function $\psi:\...
- 425
0
votes
0
answers
127
views
Extended Formulaiton and Integer Programming
An extended formulation (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a system of linear constraints
$Ex + Fy = g, y\geq 0$
in variables $(x,y)\in \mathbb{R}^{d+r}$ where $E,F$ are real
matrices ...
- 549