All Questions
46 questions
15
votes
2
answers
3k
views
Given the vertices of a convex polytope, how can we construct its half-space representation?
Let us say I have the vertices of a polytope $V = \{v_1,\dots,v_k\} \subset \mathbb R^n$. Is it possible to write $V$ as intersection of half-spaces using the information from the vertices, i.e., can ...
- 173
12
votes
1
answer
5k
views
Closest 3D rotation matrix in the Frobenius norm sense
Given a 3 by 3 matrix $M$ I would like to find the rotation matrix $R$ minimizing the Frobenius norm:
\begin{equation}
\|R-M\|_F
\end{equation}
Is there a closed form solution for $R$, or is it ...
- 561
11
votes
3
answers
6k
views
Random Sampling a linearly constrained region in n-dimensions...
Hi,
So here is my problem:
Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$
$x_n \le c_n$
and $\sum_{n=1}^N x_n = 1$ find an ...
- 113
6
votes
6
answers
3k
views
Circumference of Convex Shapes
Here is a puzzle I found in Mitteilungen der DMV (roughly, "Letters of the German Society of Mathematicians"), issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ...
4
votes
3
answers
347
views
Minimal data required to determine a convex polytope
Let $P\subset \Bbb R^d$ be a convex polytope.
Suppose that I know
its combinatorial type (aka. the face-lattice),
the length $\ell_i$ of each edge, and
the distance $r_i$ of each vertex from the ...
- 13.6k
3
votes
1
answer
328
views
LP Constraints for Connected Subgraphs of Fixed Size
Question:
how can the connectedness-constraint for a subgraph, that is induced by a proper subset $W\subset V$ of the vertices of $G(V,E),\ |V|=n,\ |W|=m$, be formulated in a $LP$ or $ILP$?
...
- 13.2k
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
19
votes
2
answers
2k
views
Is the tensor product of polyhedra a polyhedron?
Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...
- 33.8k
17
votes
3
answers
2k
views
The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$
Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum:
$$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$
...
- 2,288
10
votes
1
answer
682
views
Building a polyhedron from areas of its faces
Is there a known algorithm which, given a finite multiset (unordered list) of integers $A$, returns a yes/no answer for ...
- 6,819
5
votes
1
answer
280
views
Classification of vertex-transitive zonotopes
Zonotopes are convex polytopes that can be defined in several equivalent ways:
parallel projections of cubes,
Minkowsi sums of line segments,
only centrally symmetric faces,
...
I wonder whether ...
- 13.6k
5
votes
3
answers
1k
views
Algorithm for the intersection of a vector subspace with a cone of non-negative vectors
Hi,
I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...
4
votes
1
answer
3k
views
optimization of inverse matrix with constraint on matrix elements
everyone! I have this optimization problem with constraint.
$D$ and $T$ are symmetric matrices, where T is known and D is the unknown parameter.
$x$ and $v$ are two known p-dimensional vectors.
The ...
- 49
4
votes
1
answer
8k
views
Detection of Redundant Constraints
Suppose I pose the following query to a constraint logic programming
system:
?- Y <= 6 - X, Y <= (- 4) + 4 * X, Y <= 4 + X / 3.
Are there systems that would recognize the last inequality as
...
Countably Infinite
2
votes
0
answers
105
views
Optimization over a convex cone generated by a set is equal to optimization over the set
Within my research I found an important doubt and that prevents me from advancing, the context of my doubt is as follows:
We considerer the following optimization problem
$$
\left\{\begin{array}{cl} \...
- 159
31
votes
7
answers
3k
views
Why are we interested in permutahedra, associahedra, cyclohedra, ...?
The following families of polytopes have received a lot of attention:
permutahedra,
associahedra,
cyclohedra,
...
My question is simple: Why?
As I understand, at least the latter two were ...
- 13.6k
29
votes
6
answers
8k
views
How to find a closest integer point to the intersection of two lines?
Here's a question that originates from StackOverflow.
Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
- 391
19
votes
1
answer
928
views
Can every simple polytope be inscribed in a sphere?
It is known that not every convex polytope (even polyhedron, e.g. this one) can be made inscribed, that is, we cannot always move its vertices so that
all vertices end up on a common sphere, and
the ...
- 13.6k
19
votes
4
answers
1k
views
Applications of linear programming duality in combinatorics
So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's ...
- 997
18
votes
3
answers
3k
views
Deciding membership in a convex hull
Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$.
This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
- 667
16
votes
3
answers
1k
views
Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?
Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets.
Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.
Can $\text{Proj}(P)$ have more than $f$ facets?
...
- 163
11
votes
1
answer
351
views
Nonperiodic points of piecewise-linear homeomorphisms
Suppose $K$ is a compact polytope and $T$ is a piecewise-linear homeomorphism from $K$ to itself. Suppose also that $T$ is not of finite order (that is, for no $n \geq 1$ is it the case that $T^n(x)=x$...
- 19.7k
10
votes
2
answers
3k
views
How do you tell if a system of linear inequalities has a solution?
A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.
- 693
10
votes
1
answer
411
views
Network flows with capacities on pairs of edges
Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...
- 37.7k
9
votes
1
answer
295
views
Definition of packing property
Definition 1:
A clutter $C$ is said to have the packing property if $C$ and all of its minors satisfy the König property.
where,
vertex cover of $C$ is a set of vertices that have non-empty ...
- 381
9
votes
1
answer
2k
views
Uniform sampling from general simplex with a twist
This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange.
Given $0\leq a_1\leq\dots\leq a_D\leq1$ (all strictly positive), I want to draw points ...
- 221
8
votes
3
answers
390
views
Is there any edge- but not vertex-transitive polytope in $d\ge 4$ dimensions?
I consider convex polytopes $P\subset\Bbb R^d$. The polytope is called vertex- resp. edge-transitive, if any vertex resp. edge can be mapped to any other by a symmetry of the polytope.
I am looking ...
- 13.6k
7
votes
2
answers
1k
views
Is a given point in the interior of the convex hull of a given finite collection of points?
Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
- 96.4k
6
votes
1
answer
587
views
What are the "simplest" polytopes with an automorphism group of $\mathrm M_{11} \hspace {-1.25pt} $?
Do any polytopes have an automorphism group of the smallest of the sporadic groups, the Matthieu group $\mathrm M_{11} \hspace {-1pt} $? Indeed, they must exist. What are the simplest such polytopes ...
- 179
6
votes
1
answer
264
views
Can a dodecahedron be deformed into a great stellated dodecahedron?
Can a convex regular dodecahedron be deformed into a great stellated dodecahedron while keeping all pentagons planar and all edges of nonzero length the whole time?
- 2,773
6
votes
2
answers
8k
views
Existence/Uniqueness of Nonnegative Solutions of Linear Systems of Equations
Suppose we have an $m$x$n$ matrix $A$, with $m\lt n$, and an $m$x$1$ vector $b$. Are there existence and uniqueness conditions characterizing nonnegative solutions of the system of linear equations $...
6
votes
1
answer
212
views
A polytope with congruent facets and an insphere that is not facet-transitive?
Is there a $d$-dimensional convex polytope (convex hull of finitely many points, not contained in a proper subspace), with $d\ge 4$ and the following properties?
All facets are congruent,
it has an ...
- 13.6k
6
votes
1
answer
761
views
Checking if one polytope is contained in another
I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other.
At the moment I am ...
- 491
6
votes
1
answer
609
views
Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers
Let $a(n)$ be the Dirichlet inverse of the Euler totient function:
$$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$
and let the matrix $T(n,k)$ be:
$$T(n,k)=a(\gcd(n,k)) \tag{2}$$
It has been ...
- 1,183
4
votes
2
answers
2k
views
Simplified knapsack problem
There is a problem that I can not solve.
Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...
- 41
4
votes
1
answer
891
views
Basic result in semi-infinite linear programming
Consider a standard linear program of the form $$\textrm{minimize}_x~~~~ c^Tx~~~~ s.t. \\ Ax = b \\ x \geq 0$$ with $x\in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$. It is well known that, if ...
- 4,049
4
votes
1
answer
204
views
Reference: Packing under translation is in NP
I am looking for a reference for a result that I am aware of.
Let me describe the result.
Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP
time, if $p_1,\ldots,p_n$ can be ...
- 479
3
votes
2
answers
792
views
complexity of finding optimal matchings of given fixed size
It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in ...
- 13.2k
3
votes
1
answer
289
views
On decomposition of polytopes
Given $m$ number of convex polytopes each with $v$ vertices and described by $h$ hyperplane inequalities in $\mathbb R^t$ are there operations on these polytopes that combine then to give an $v^{\...
- 1,826
3
votes
4
answers
4k
views
Existence of nonnegative solutions to an underdetermined system of linear equations
Similar questions have been asked elsewhere, but I think this is sufficiently different to warrant a new post. I have a particular matrix $A$ and would like to know when the system $Ax = 0$ has at ...
- 491
2
votes
1
answer
137
views
Design constraint systems over the reals
This question is inspired by the discussion at this problem.
Suppose I have a design consisting of a finite point set $U$ of size $|U|=m_{\emptyset}$ and a family of $n$ subsets (sometimes called ...
- 30.1k
2
votes
3
answers
2k
views
non-convex Polytope definition
I have a simple question. I read that given a vector space $N_{\mathbb{R}}$ over $\mathbb{R}$,
we can define a convex polytope in the following way:
$$P:= \Big\{ \sum_{u\in S} \mu_u u \,\Big| \, \...
- 335
2
votes
2
answers
403
views
Is this a linear optimization problem? $Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative
$Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative.
What should $A$ satisfy to guarantee the equation set have only zero solution?
- 23
2
votes
0
answers
94
views
Dodecahedron deformation II
(Follow-up to this question)
Can a dodecahedron be deformed into a great stellated dodecahedron while maintaining the number of dimensions each element occupies?
- 2,773
2
votes
1
answer
2k
views
Finding a point farthest away from $k$ points in a polygon
There are $k$ points placed inside a polygon and I am interested in finding a point inside the polygon (not necessarily on its boundary) who's minimum distance to any of the $k$ points is maximized.
...
- 57
1
vote
0
answers
46
views
Non-negative polynomials $f(p), p\in P$ from Polynomial ideal where $P$ compact polytope?
Partially related to Non-negative Polynomials from Polynomial Ideal? where focus on graph theory but now I want to understand more generally how to determine non-negativity in more general case.
A. ...
- 143