Questions tagged [convex-geometry]
The convex-geometry tag has no usage guidance.
44
questions
3
votes
1
answer
100
views
Strongly polynomial time algorithm for shortest convex combination
Problem: Let $S$ be a finite set of vectors. Let $C$ be their convex hull. Compute $\operatorname{argmin}_{x \in C} \|x\|$.
Reference 1 gives an algorithm for this problem that is finite-time (Section ...
- 642
4
votes
1
answer
187
views
Restriction of a convex function to {0, 1}^n
Suppose I have a real-valued convex function $f$ on the unit hypercube $[0,1]^n$, and let $\bar{f}$ be its restriction to the integer points $\{0,1\}^n$. Does $\bar{f}$ satisfy any properties, or can ...
- 43
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
5
votes
1
answer
89
views
Complexity of computing the union of H-polytopes in three dimensions
Consider a set $P_1,\ldots,P_k$ of polytopes in $\mathbb{R}^3$, each given as an intersection of halfspaces with rational normals (in particular, they are all convex).
We are also given a target ...
- 5,511
3
votes
1
answer
214
views
Minimal number of hyperplanes needed to separate sets of points from one other set
Let $\mathbb{R}^d$ be our space. We have a single good set of points $g$, and a collection of bad sets of points $B$.
We assume that for all $b \in B$ the convex hulls of $g$ and $b$ are disjoint. ...
- 690
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
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
10
votes
1
answer
254
views
Is this "subgroup packing" polytope integral?
Let $\Gamma$ be a finite abelian group, and let $P$ be the polytope in $\mathbb{R}^\Gamma$ defined to be the points $x$ satisfying the following inequalities:
$$\begin{array}{cl}
\sum_{g\in G} x_g \...
- 1,419
6
votes
1
answer
162
views
Embedding points in Euclidean space into a box
If I give you a set of points in Euclidean space, is there a criterion to determine whether there exists a (potentially higher-dimensional) rectangular prism / box that has these points as their ...
- 61
2
votes
1
answer
63
views
Finding a cell in an arrangement of simplices
My question is n-dimensional, but I will begin by dropping the problem down to two dimensions for clarity's sake. It regards defining what is a solution by defining one or more data points that are ...
- 123
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
1
vote
0
answers
87
views
Do nested convex bodies have increasing "Volume/Surface Area" ratios? [closed]
Suppose we have two convex bodies $A$ and $B$, where $A \subseteq B$. Is it always true that $\mathrm{Vol}(A)/\mathrm{SurfaceArea}(A) \leq \mathrm{Vol}(B)/\mathrm{SurfaceArea}(B)$?
It's true in all ...
- 19
5
votes
2
answers
222
views
Voronoi Diagram of Lines
Let $S$ be a set of lines (or line segments) in $\mathbb{R}^3$. Consider the Voronoi diagram $VD(S)$. The best lower bound on the complexity of $VD(S)$ is $\Omega(n^2)$ and the best upper bound is $O(...
- 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
7
votes
1
answer
561
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 \...
- 1,345
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
2
votes
1
answer
247
views
When can a convex function induce submodularity?
Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$. Let $f'$ be the induced function on the discrete hypercube $\{-1,1\}^n$. Now I want to find a vertex on $\{-1,1\}^n$ on which ...
- 644
1
vote
1
answer
106
views
Assignment of values for a set
Consider the following problem:
Input: the vertices of two $n$ dimensional axis-parallel cubes:
$\times_{i=1}^{n} [a_i,b_i] \subseteq [0,1]^n$ and
$\times_{i=1}^{n} [l_i,u_i] \subseteq [0,1]^n$.
...
- 253
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
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
8
votes
2
answers
4k
views
A Question on Convex Conjugate Duality for KL Divergence
The convex conjugate of a function, say, $f:X\mapsto \mathbb{R}$ is a function $f^*:X^*\mapsto \mathbb{R}$ defined as
$$f^*(x^*):=\sup_{x\in X} ~\langle x, x^*\rangle-f(x),$$ where $X^*$ is the ...
- 425
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
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
3
votes
1
answer
132
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 ...
- 531
6
votes
1
answer
270
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.
...
- 335
3
votes
1
answer
276
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 ...
- 151
4
votes
1
answer
144
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 ...
- 3,940
9
votes
1
answer
409
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 ...
- 10.2k
4
votes
1
answer
194
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 ...
- 6,960
4
votes
2
answers
193
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 ...
- 549
2
votes
0
answers
88
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 \...
- 195
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
1
vote
1
answer
112
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 + ...
- 549
4
votes
1
answer
133
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 ...
- 41
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
14
votes
1
answer
839
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 ...
- 31.9k
4
votes
2
answers
3k
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 ...
- 1,581
8
votes
2
answers
214
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 ...
- 1,195
9
votes
1
answer
488
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 $...
- 91
13
votes
2
answers
503
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$ ...
- 10.2k
23
votes
3
answers
730
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 ...
- 1,574
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 ...
9
votes
1
answer
1k
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 $d$-...
- 1,468