The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
0answers
161 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 ...
8
votes
0answers
125 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, ...
3
votes
1answer
103 views

Efficient algorithm for computing equally distributed points in polytope?

Given a $d$-dimensional (rational) convex polytope $P$ with vertices $v_1, \ldots, v_n$, I would like to compute many equally distributed points that lie in $P$. "Equally distributed" is of course not ...
6
votes
1answer
141 views

Why is the first step in the Lovasz-Vempala convex volume algorithm correct?

I've been reading about convex volume estimation, and have found the paper "Simulated Annealing in Convex Bodies and an $O^{*}(n^4)$ Volume Algorithm" by Lovasz and Vempala, which can be read here. ...
3
votes
1answer
255 views

Algorithm for testing if a point belongs to a sequence of convex set or not

I have a sequence of convex sets $C_\lambda$ for $\lambda \in \mathbb{R}$ such that for $\lambda_1 > \lambda_2$, we have $C_{\lambda_1} \subset C_{\lambda_2}$ (essentially a nested sequence of ...
2
votes
0answers
96 views

Batch membership testing for convex polyhedron specified in vertex representation

I have a convex shape defined by a set of vertices (the so-called vertex representation of a convex polyhedron). I also have a large set of points and I would like to test which are contained in the ...
6
votes
0answers
120 views

VC dimension of Voronoi cells in R^d?

Suppose I have $k$ points in $\mathbb{R}^d$. These induce a Voronoi diagram. If I assign to each of the $k$ points a $\pm$ label, these induce a binary function on $\mathbb{R}^d$. Question: what is ...
4
votes
1answer
142 views

Configurations from arrangement of lines

Suppose we have an arrangement of $n$ lines in the plane. This partitions the plane into regions. We can label each region by a string in $\{+1, -1\}^n$, where the $i$'th coordinate is +1 if the ...
3
votes
2answers
131 views

On facets of 01-polytope

$0,1$-polytopse are fundamental objects in combinatorial geometry and comvex optimization. I am interested in the size of binary representation of hyperplanes to use in the framework of computational ...
2
votes
0answers
80 views

Helly's number from biconvex functions [closed]

Helly's Theorem states the following. Suppose $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq ...
1
vote
0answers
95 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
96 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
104 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
187 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
338 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
638 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
182 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
298 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 ...
12
votes
2answers
392 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
677 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
228 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 ...
7
votes
1answer
739 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 ...