All Questions
739 questions
13
votes
3
answers
834
views
Famous theorems that are special cases of linear programming (or convex) duality
The max flow-min cut theorem is one of the most famous theorems of discrete optimization, although it is very straightforward to prove using duality theory from linear programming. Are there any ...
13
votes
0
answers
573
views
What are the known convex polyhedra with congruent faces?
Note: I originally asked this question on math.SE here, where I posted a bounty on the question but received no answers after a week despite apparent interest in the problem. I'm hoping MathOverflow ...
- 3,068
13
votes
0
answers
406
views
Surface area of convex hull [duplicate]
Let Q be the convex hull of a non-convex polyhedron P. Is it true that the surface area of Q is not greater than the surface area of P?
- 131
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
2
answers
2k
views
Great polyhedra: What does "great" signify?
Great Cubicuboctahedron
Great Icosacronic Hexecontahedron
Great Rhombic Triacontahedron
Great Snub Icosidodecahedron
Great Stellated Dodecahedron
Great Triakis Octahedron
...
There are many polyhedra ...
- 151k
11
votes
2
answers
963
views
Why is modular forms applicable to packing density bounds from linear programming at $n\in\{8,24\}$?
Sphere packing problem in $\mathbb R^n$ asks for the densest arrangement of non-overlapping spheres within $\mathbb R^n$. It is now know that the problem is solved at $n=8$ and $n=24$ using modular ...
- 1,826
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
11
votes
2
answers
455
views
Dodecahedral rolling distance
Let a dodecahedron sit on the plane,
with one face's vertices on an origin-centered unit circle.
Fix the orientation so that the edge whose indices are $(1,2)$ is horizontal.
For any $p \in \mathbb{R}...
- 151k
11
votes
3
answers
3k
views
polyhedra with equilateral pentagons faces
In page http://loki3.com/poly/isohedra.html around six polyhedra with equilateral pentagons as faces are shown: a pyritohedron, icositetrahedrons... Is there a complete list of this kind of polyhedra? ...
- 111
11
votes
2
answers
1k
views
Floating polyhedra with fair equilibria
Is there a homogeneous convex polyhedron
which floats so that some subset (perhaps all) of its faces
is distinguished as "up" (above the water line)
in stable equilibrium, each face with equal ...
- 151k
11
votes
2
answers
1k
views
Which (semi)regular polyhedra are combinations of two others?
The convex combination of convex polytopes is a convex polytope.
An example in $\mathbb{R}^2$ is that a regular octagon
can be obtained as $\frac{1}{2} S + \frac{1}{2} S'$,
where $S$ is a square and $...
- 151k
11
votes
1
answer
211
views
Is it possible for the dihedral angles of a polyhedron to all grow simultaneously?
(Originally on MSE.)
Suppose $P$ and $Q$ are combinatorially equivalent non-self-intersecting polyhedra in $\mathbb{R}^3$, with $f$ a map from edges of $P$ to edges of $Q$ under said combinatorial ...
- 3,068
11
votes
1
answer
651
views
How to correctly state Cauchy's rigidity theorem?
Cauchy's rigidity theorem is often stated briefly as
Any two (convex, 3-dimensional) polyhedra with pairwise congruent faces are themselves congruent.
As a more formal generalization to general ...
- 13.6k
11
votes
2
answers
489
views
Shortest morphing between shapes embedded in $\mathbb{R}^3$
I am interested in what in computer graphics is called
morphing between two topologically equivalent shapes $S_0$
and $S_1$ in 3D.
This is a continuous "path" of shapes $S_t$, each embedded and
all ...
- 151k
11
votes
0
answers
328
views
How many ways to flatten a Tesseract onto a table?
A cube can be cut and flattened out onto a table in a way that the faces stay connected and none of them overlap. There are $384$ ways to make the cuts and $11$ distinct meshes emerge (see here). And ...
- 171
11
votes
0
answers
726
views
Making a convex polyhedron with two sheets of paper
Suppose that we have two sheets of paper $S,T$ and that each of $S,T$ is in the shape of a convex quadrilateral. Also, suppose that the length of the perimeter of $S$ equals that of $T$. (Note that $S$...
- 4,757
10
votes
2
answers
523
views
When does every point in a polytope lie along a chord between its edges?
Consider the 3-simplex, or tetrahedron, in 3-space. Regardless of the positions of the vertices, every point in the simplex lies on a chord between two non-adjacent edges of the simplex. Or, ...
- 329
10
votes
3
answers
2k
views
On maximal regular polyhedra inscribed in a regular polyhedron
Let T, C, O, D, or I be regular tetrahedron, cube, octahedron, dodecahedron, and icosahedron, respectively. Suppose that the outer polyhedron have edge-length 1.
For example, it's easy to prove that ...
- 4,757
10
votes
2
answers
387
views
What is Kept Fixed for Flexible Spheres
For background to this question much recent exciting related things, see this videotaped lecture by Alexander Gaifullin.
Consider a triangulation $K$ of a two-dimensional sphere and consider maps ...
- 24.7k
10
votes
2
answers
326
views
Do maximal polyhedra have algebraic volume?
Is it possible to prove that for every $n > 3$ the maximal possible volume of a convex polyhedron having $n$ vertices inscribed in a sphere of unit radius is an algebraic number?
Update: What can ...
- 6,819
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
623
views
Polyhedron not circumscribed about a sphere
Let $P$ be a polyhedron whose faces are colored black and white so that there are more black faces and no two black faces are adjacent. Show that $P$ is not circumscribed about a sphere.
My teacher ...
- 1,090
10
votes
2
answers
902
views
Cut and Fold Polyhedron!
I have two convex polyhedra such that their sums of side areas are equal. It is true that I can cut one of them and flatten it on the plane, then fold the flattened polygon to reach the other ...
- 628
10
votes
1
answer
3k
views
Computionally efficient vertex enumeration for (convex) polytopes
Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The vertex enumeration problem asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be ...
- 321
10
votes
3
answers
6k
views
Solving a system of linear inequalities -- what is the dimension of the solution set?
It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$?
For the applications I have in mind the ...
- 7,857
10
votes
1
answer
565
views
The intersection of two $l_1$ balls
Let $B_1$ and $B_2$ be two balls in $\mathbb{R}^n$ with respect to the $l_1$ norm that have different radii and different centers. Is there an upper bound for the number of vertices that $B_1\cap B_2$...
- 131
10
votes
2
answers
369
views
Do Bernoulli polynomials know about face vectors?
This question is grounded firmly in numerology. It originates in an observation about some Bernoulli polynomials and the regular icosahedron. Let $F_{k+1}(n)=\sum_{i=1}^n i^k$ be the sum of the ...
- 1,277
10
votes
1
answer
426
views
Complexity of the union of randomly rotated unit cubes
It is a remarkable fact that the union of congrent cubes
has only at most near-quadratic combinatorial complexity,
$O^*(n^2)$ for $n$ cubes, known to be almost tight.
This contrasts with the union of ...
- 151k
10
votes
1
answer
2k
views
Sum of difference moduli vs. sum of modulus differences
This is a failed attempt of mine at creating a contest problem; the failure is in the fact that I wasn't able to solve it myself.
Let $x_1$, $x_2$, ..., $x_n$ be $n$ reals. For any integer $k$, ...
- 33.8k
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
10
votes
0
answers
722
views
Fractional Matching version of Hall's Marriage theorem
Let $G=(S,T,E)$ be a bipartite graph, $|S|=|T|$. Then the following are equivalent:
1) there exist a perfect matching in $G$;
2) there exist non-negative weights on edges such that the sum of ...
- 109k
10
votes
0
answers
333
views
Bi-spherical polyhedra
Bicentric polygons have been studied: a polygon all of whose vertices lie on its
circumcirle, and whose incircle is tangent to every edge:
I have not been able to find a comparable literature ...
- 151k
9
votes
3
answers
436
views
Labeling edges of an icosahedron with sum constraints
The question is inspired by this previous MO question. There it was shown that it's possible to label the edges of a cube by the numbers $\{1,2,\ldots,6,8,9, \ldots, 13\}$ in such a way that:
Three ...
- 20.8k
9
votes
1
answer
6k
views
Proving that a binary matrix is totally unimodular
I'm working on a set of problems for which I can formulate binary integer programs. When I solve the linear relaxations of these problems, I always get integer solutions. I would like to prove that ...
- 213
9
votes
1
answer
3k
views
Inverse of a totally unimodular matrix
A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$.
A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. A ...
- 93
9
votes
2
answers
843
views
How did they come up with the MRRW bound?
Among the good asymptotic bounds in coding theory in the MRRW bound. It is obtained by using the linear programming problem of Delsarte's and providing a solution. The LP problem is
Suppose $C \...
- 885
9
votes
1
answer
436
views
The $32$-deg polynomial for the tetrahedron inscribed in the icosahedron?
This MO answer discusses this table involving the maximal side lengths of the five Platonic solids $T,C,O,D,I$ inscribed in the other solids,
This table is also found in Moritz Firsching's paper. I ...
- 12.6k
9
votes
2
answers
341
views
Are there centrally-symmetric self-dual polytopes in dimension $d> 4$?
A convex polytope $P\subset\Bbb R^d$ is centrally symmetric if $-P=P$. It is self-dual (or better, self-polar?) if its polar dual $P^\circ$ is congruent to $P$, that is, there is a map $X\in\mathrm O(\...
- 13.6k
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
282
views
Thinnest covering of the plane by regular pentagons
Q. Is it known what is the thinnest covering of the infinite plane by regular pentagons?
By covering I mean every point of the plane is covered.
By thinnest I mean the proportion of the plane covered ...
- 151k
9
votes
1
answer
519
views
If we know the combinatorics of a polyhedron, and all but one of its dihedral angles, does that uniquely determine the remaining dihedral angle?
If we know the combinatorics of a polyhedron, and all but one of its dihedral angles, does that uniquely determine the remaining dihedral angle?
I’m happy to assume the polyhedron is simply connected, ...
- 2,896
9
votes
2
answers
1k
views
Fractal Tiling of Rhombic Dodecahedra
Hello, this is my first question on Math Overflow...
Rhombic dodecahedra can be tiled in 3-space, leaving no gaps. This tiling corresponds to the close-packing of spheres.
Consider a "nucleus" ...
user24228
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
9
votes
4
answers
475
views
Uniform Sampling Subject to Linear Equalities and Non-Negativity Constraint
I'm trying to sample uniformly on the intersections of faces of several simplicies, with all coordinates being non-negative. That is, given constraints
$$A\vec{w}=\vec{b} \ \ and \ \ \vec{w} \geq \vec{...
- 191
9
votes
0
answers
1k
views
Maximum volume cross-section of a hypercube
This is surely well known, but:
Q1. What is the $(d{-}1)$-dimensional polytope
that realizes the maximum volume cross-section of a unit hypercube
by a $(d{-}1)$-dimensional hyperplane?
...
- 151k
9
votes
0
answers
543
views
Maximum volume convex body coverable by a unit square
Suppose you are given a single unit square, and you are permitted to cut it into $k$ (connected)
pieces (where $k=1$ means just the square). Your task is to construct the largest volume
convex body ...
- 151k
8
votes
7
answers
2k
views
Visualizing polyhedra from their 1-skeletons
Except for a few simple cases (typically pyramids and prisms) I find it hard to visualize a polyhedron from its 1-skeleton embedded in the plane, e.g. the hexahedral graph 5, as can be seen here.
...
- 9,720
8
votes
1
answer
1k
views
Two questions on the permutohedron
The $n$-dimensional permutohedron $P_n$ is the polytope given by the convex hull of all the possible permutations of the vector $(1,2,\dots,n+1)\in\mathbb{R}^{n+1}$. So it has $(n+1)!$ vertexes.
I ...
user82886
8
votes
1
answer
443
views
Convex Polyhedra Scissors Congruence Problem
I am currently writing a geometry paper "Rectifications of Convex Polyhedra" and I am confused to have discovered what appears to be a remarkable discrete geometric fact:
Conjecture: Let $P$ be a ...
- 1,431
8
votes
3
answers
793
views
Efficient topological triangulations of non-convex polyhedra
Does every polyhedron in $\mathbb{R}^3$ with $n$ triangular facets have a topological triangulation with complexity $O(n)$?
Suppose $P$ is a non-convex polyhedron in $\mathbb{R}^3$ with $n$ ...
- 436