The convex-geometry tag has no wiki summary.
1
vote
0answers
75 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 ...
1
vote
1answer
78 views
Expressing a set of 0-1 strings by Extended Formulation
Extended Formulation of a polytope $P \subseteq \mathbb{R}$ is a system of linear constraints which satisfies the following condition:
$x \in P \iff \exists y\in \mathbb{R}^{d} \mbox{ such that } Ax ...
3
votes
1answer
84 views
Balanced partitioning of a set of axis-parallel 2D rectangles
Fix a constant $0<\alpha<1/2$. The problem is the following. Suppose there are $N$ axis-parallel rectangles on the 2D plane with weights $w_1, w_2,\ldots, w_N$ and with coordinates all in the ...
11
votes
0answers
176 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}\ ...
14
votes
1answer
224 views
Computing the Löwner-John ellipsoid of a polyhedron
The Löwner-John ellipsoid of a convex set $C$ is the minimum-volume ellipsoid (MVE) that encloses it. The ellipsoid can be computed using Khachiyan's method, and there are a number of approximations ...
2
votes
2answers
203 views
Minimizing the maximum dot product among k unit vectors in an n-dimensional space
Suppose, we are given a set of $k$ unit vectors $v_1,\ldots,v_k$ in $\mathbb{R}^n$. Consider all possible dot products among distinct vectors $v_i \cdot v_j$, where $i \ne j$. Let,
$$\alpha = \max_{1 ...
8
votes
2answers
176 views
Generating a point in a rational polytope $P \subseteq R^k$ given a point in $P^\epsilon$
Consider a rational polytope $P$ that is defined by means of a separation oracle. That is, $P$ can be described implicitly as $P = \{x \in R^k: Ax \leq b, A \in Z^{m \times k}, b \in Z^m \}$, but ...
9
votes
1answer
249 views
Algorithm for approximating convex bodies by a convex hull of ellipsoids
I am working in the field of structural engineering and I would like to find an efficient algorithm to construct an approximation (in the Hausdorff metric) of a convex body $K$ by the convex hull of ...
11
votes
2answers
340 views
Learning triangles in the plane
I assigned my students the problem of finding a triangle consistent with a collection of $m$ points in $\mathbb{R}^2$, labeled with $\pm1$. (A triangle $T$ is consistent with the labeled sample if $T$ ...
23
votes
3answers
652 views
Convex Body with minimum expected l2 norm
Consider a convex body $K$ centered at origin and symmetric (i.e. if $x\in K$ then $-x\in K$). I desire to find a different convex body $L$ such that $K\subseteq L$ and the following measure is ...
5
votes
0answers
193 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 ...
6
votes
1answer
432 views
Computing volume of high-dimensional convex polyhedra
I am looking for software for computing/estimating volume of high-dimensional convex polyhedra. More specifically, I am interested in a program, which can handle bodies with $n$ vertices in ...
