Questions tagged [convex-polytopes]
Convex polytopes are the convex hulls of a finite set of points in Euclidean spaces. They have rich combinatorial, arithmetic, and metrical theory, and are related to toric varieties and to linear programming
918
questions
1
vote
2
answers
126
views
An optimality condition for the corners of convex polytopes?
Let $H,H'\subset\mathbb{R}^m$ be two hyperplanes with unit normal-vector,
and let $P\subset\mathbb{R^m}$ be a convex polytope (defined via its corners $v_0, ... , v_n$, where $n\ge m$).
Let's ...
- 12.7k
7
votes
1
answer
198
views
How to prove the existence of the polytope in $\mathbb{R}^d$ with a given number of faces, minimizing the isoperimetric ratio?
This is the isoperimetric type question. We know that in $\mathbb{R}^d$, balls are the sets that minimize the isoperimetric ratio $\frac{S^{d}}{V^{d-1}}$, where $S$ is the surface area and $V$ is the ...
- 1,320
4
votes
0
answers
264
views
Prove or disprove a claim about covering a polytope by convex polytopes in a certain way
Here is the claim:
Given a polytope $K$ in a unit ball in $\mathbb{R}^d$, there exists a universal constant $C(d)>0$ depending only on $d$ and a countable collection of convex polytopes $\{K_i\}_{...
- 1,320
9
votes
4
answers
437
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
11
votes
2
answers
550
views
Book on the tetrahedron
Does anybody know of a book containing "all you want to know about the tetrahedron"? What you want to know should include basic geometry of the tetrahedron, study of orthocentric tetrahedra, the Monge ...
- 4,382
6
votes
1
answer
326
views
Measurement of "symmetry" of a convex body
I often hear that the regular simplex is "the least" symmetric convex body, and I've heard that there are some measures of symmetry of a body, that the simplex minimizes.
Could you please explain or ...
- 1,873
5
votes
2
answers
181
views
Differentiability of polytope shadow areas
Let $P$ be an opaque convex polyhedron containing the origin in $\mathbb{R}^3$,
and let $S$ be an origin-centered sphere strictly containing $P$: $S \supset P$.
For a point $x$ on $S$, let $\sigma(x)$ ...
- 149k
0
votes
1
answer
123
views
polynomial expression for counting number of integral points of a set
Let $v_i=a_ie_i\in\mathbb R^d$ and $w_i=b_ie_i\in\mathbb R^d$ for $i=1,\dots,d$ where $e_i$'s are unit vetcors and $a_i,b_i$ are positive integers. Let $$S=conv\{0,rv_i+sw_i:i=1,\dots,d\}.$$
Can we ...
- 1,703
1
vote
0
answers
167
views
About properties of polynomials with common interlacing
Say $\{a_1,a_2,..,a_n\}$ and $\{b_1,b_2,...,b_n\}$ be the real roots of two monic polynomials of degree $n$ which have a common interlacing. (say I have arranged the roots in increasing order)
Can ...
- 555
2
votes
1
answer
131
views
Efficient algorithm for finding normals of a high dimensional convex hull with few facets
I am looking for the most efficient algorithm to use to, given a set of points in $d$ dimensional space, find the normals of the convex hull of these points, given that I know that the number of ...
4
votes
2
answers
140
views
Expressing a convex Polytope as a sublevel set of a function
Given an n-dimensional polytope $P$ in $\mathbb R^n$, Given as a convex hull of a finite set of points, $S$ I would like to construct an expliict formula for a function $f\colon \mathbb R^n \to \...
- 1,873
2
votes
0
answers
388
views
Find the intersection between two convex hulls, in this specific case
We work over $\mathbb{R}^K$. Let $V$ be the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$.
Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ ...
- 223
2
votes
0
answers
239
views
Newton polyhedron and product of ideals
Let $I$ be an ideal generated by monomials $\underline{x}^{\underline{a}_1},\ldots ,\underline{x}^{\underline{a}_s}$ and
$J$ be the ideal generated by $\underline{x}^{\underline{b}_1},\ldots ,\...
- 1,703
2
votes
2
answers
326
views
Cardinality of non-integer points in the translation of the Minkowski sum of convex hull.
Let $\operatorname{conv}(a_1,\ldots,a_m)$ denote the convex hull of $\{a_1,\ldots,a_m\}$. Let $\mathbb{Z}_+=\mathbb{N}\cup\{0\}$ and $\mathbb{Q}_+$ denotes the positive (inluding 0) rational numbers. ...
- 1,703
1
vote
1
answer
989
views
Extreme points of convex hull of Minkowski sum [closed]
Let $\operatorname{conv}(a_1,\ldots,a_m)$ denote the convex hull of $\{a_1,\ldots,a_n\}$. Let $P = \operatorname{conv}(a_1,\ldots,a_p)$ and $Q = \operatorname{conv}(b_1,\ldots,b_q)$ be two convex sets ...
- 1,703
1
vote
0
answers
50
views
Projection of a ray onto a random polytope
Suppose $P$ is a polytope formed by $p$ (general) random planes in $\mathbb{R}^n$. We assume $p \asymp n$ and $P$ has a diameter $O(\sqrt{n})$. For any $x \in \mathbb{R}^n$, denote by $\operatorname{...
- 753
55
votes
5
answers
2k
views
Do unit quaternions at vertices of a regular 4-simplex, one being 1, generate a free group?
Choose unit quaternions $q_0, q_1, q_2, q_3, q_4$ that form the vertices of a regular 4-simplex in the quaternions. Assume $q_0 = 1$. Let the other four generate a group via quaternion ...
- 21.5k
8
votes
2
answers
485
views
Integer decomposition of dilated integral polytopes
For $n > 0$, let $P$ be an integral polytope, that is, the convex hull in $\mathbb{R}^n$ of points in $\mathbb{Z}^n$. Suppose that $\dim(P) = n$.
Question: Given $d > n + 2$ is it true that
$$ ...
- 83
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
2
answers
795
views
Largest regular $k$-simplex inscribed in a $d$-cube, $k < d$
The largest (by edge length) regular simplex inscribed in a unit cube
is well known in $\mathbb{R}^2$ and $\mathbb{R}^3$:
Image sources:
left: NMSU,
right: Mathworld.
A recent Amer ...
- 149k
8
votes
2
answers
533
views
Decomposition of a cross-polytope into simplices
Consider the standard embedded $n$-cross polytope $P_n$ with vertices $\pm e_i \in \mathbb R^n$. Let us consider decompositions of this polytope into $2^{n-1}$ simplices, such that these simplices ...
- 11.9k
2
votes
2
answers
159
views
4D Duoprisms based on nonconvex polygons
A duoprism is a polytope
that can be expressed as the Cartesian product of two polytopes (each of dimension $\ge 2$).
Four-dimensional duoprisms in particular have been studied:
$$P \times Q = \{ (...
- 149k
13
votes
2
answers
462
views
Can any simplex shadow-project to a regular simplex?
Every triangle $A$ can be oriented in $\mathbb{R}^3$
so that its orthogonal projection (shadow) onto the $xy$-plane is an
equilateral triangle $Q$:
&...
- 149k
18
votes
5
answers
761
views
How many unit simplices are needed to cover a unit $n$-cube?
The volume of an $n$-dimensional simplex of unit edge length is
$$V(n) = \frac{\sqrt{n+1}}{n! 2^{n/2}} \;,$$
so at least $\lceil 1/V(n) \rceil$ such simplices are needed to cover the unit $n$-cube.
...
- 149k
4
votes
0
answers
217
views
Intersection numbers on blow ups of toric varieties
Suppose we have a smooth, complete toric varietiy $X_{\Sigma}$ of dimension $n$. Let $\sigma_k \in \Sigma(k)$ a smooth $k$-dimensional cone in $\Sigma$ and suppose we make the toric blow up at the ...
- 337
3
votes
1
answer
138
views
convex decompositions of the sphere
Consider a decomposition of the sphere $S^n$ into convex pieces (that is, every cell of the cell decomposition is convex, in particular, is contained in a hemisphere). Consider the $k$-skeleta of ...
- 95.6k
3
votes
0
answers
109
views
Polytopes whose intersections have few vertices
This is related to one that I asked earlier:
The intersection of two $l_1$ balls
My question: are there any general classes of polytopes $P_1,P_2\subset\mathbb{R}^n$ such that $P_1$ has few ...
- 131
10
votes
1
answer
546
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
1
vote
0
answers
89
views
Volume under the intersection of scaled simplices
This is rather specific but I need to compute the volume under the intersection of rescaled simplexes, that is, the volume of the space:
$\left\{x \in \mathbb{R}^n|\sum_i c_{ki} |x_i| \leq1\; k = 1 \...
3
votes
2
answers
112
views
algorithm of polytope
Basically, we have an incremental sets of vertices
$${V_1} \subset {V_2} \subset ...$$
for each of them, we could build a polytope $${P_i} = Conv({V_i})$$
Consequently, we can compute
$${F_i} = ...
- 867
1
vote
0
answers
80
views
A version of isotone projection cones
We write $a \succeq b$, where both $a, b \in \mathbb{R}^n$, as a shorthand for $a_i \ge b_i$ for all $1 \le i \le n$. Let $C$ be a closed convex cone in the first orthant of $\mathbb{R}^n$ and denote ...
- 753
2
votes
0
answers
92
views
A convex analysis theorem improvement
John's theorem states that to any full-dimensional symmetric convex set $K\subseteq R^n$ and any Ellipsoid $E\subseteq R^n$ that is centered at origin, there exists an invertible linear map $T$ so ...
- 13.7k
3
votes
0
answers
143
views
Does a polytope have a self-indexing shelling?
If $X$ is a smooth projective toric variety and $P \subset \mathbf{R}^n$ is its moment polytope, then a generic linear function on $\mathbf{R}^n$ induces (1) a Morse function on $X$, and (2) a ...
- 4,849
1
vote
1
answer
2k
views
Computation of extreme rays of rational polyhedral cones - Hemmecke's project and lift algorithm
I am working on an implementation of Raymond Hemmecke's algorithm for finding generating sets of cones: http://arxiv.org/abs/math/0203105
Unfortunately I am struggling to make the algorithm work on ...
- 11
1
vote
1
answer
147
views
number of affine pieces of linear interpolation of convex functions in high dimension
Consider a convex function $f$ defined on a $d$-dimensional hypercube $[0,1]^d$. Now for fixed $m \in \mathbb{N}$, consider the grids $\mathcal{G}_m=\{(i_1/m,\cdots,i_d/m)\}$ where $i_\alpha\in\{0,1,\...
- 589
4
votes
0
answers
269
views
Which (polytopal) fans/polytopes are secondary?
Let $P$ be a (d-1)-dimensional polytope with $n$ vertices that sits in an affine hyperplane in $\mathbb{R}^d$.
The secondary fan of $P$ is a polytopal fan in $\mathbb{R}^n$ with $d$-dimensional ...
- 882
3
votes
2
answers
171
views
Polytope with indegree-increasing property.
I have a question about a simple polytope.
I am worried that my question would be inappropriate for mathoverflow.
So I am sorry that I am ignorant of combinatorics.
Let $\mathcal{P}$ be a simple ...
- 1,037
27
votes
3
answers
12k
views
Which unfoldings of the hypercube tile 3-space: How to check for isometric space-fillers?
Recently Mark McClure constructed and displayed
the 261 unfoldings of the hypercube (tesseract)
in response to the question,
"3D models of the unfoldings of the hypercube?":
The first 9 unfoldings ...
- 149k
5
votes
2
answers
1k
views
regular polyhedra (and polytopes) in hyperbolic geometry, and generalisations
While there exist regular tesselations of the hyperbolic plane with arbitrary regular polygons, there are no new regular polyhedra in hyperbolic (3D) space. This being quite trivial, it is probably ...
- 3,560
7
votes
1
answer
981
views
Approximation of convex body by polytopes
In a recent survey paper, Approximation of convex sets by polytopes, Bronstein claims that under Hausdorff distance $\rho_H$, for every convex body $U$,
$$\rho_H(U,\mathcal{P}_n)\leq c(U) n^{-2/(d-1)},...
- 589
8
votes
0
answers
178
views
Can the GUE be thought of as a uniform point in a high-dimensional polytope
I have thought about this question for a long time and could only find partial answers.
The Gaussian Unitary Ensemble (or GUE) is the eigenvalues of a random Hermitian matrix with complex Gaussian ...
- 22.6k
26
votes
2
answers
4k
views
3D models of the unfoldings of the hypercube?
There are (apparently) 261 distinct unfoldings of the 4D hypercube, a.k.a., the
tesseract, into 3D.1
These unfoldings (or "nets") are analogous to the 11 unfoldings of
the 3D cube into the plane.2
...
- 149k
6
votes
1
answer
601
views
Maximal volume of a simplex inscribed in a spherical cap
Let $B_n$ be the $n$-dimensional unit ball, and $B_n(\varepsilon)$ be the spherical cap with height $\varepsilon$ I am interested in the quantity
$$\Gamma:=\sup_{\Delta:\textrm{ inscribed simplex in }...
- 589
1
vote
0
answers
59
views
Conditions on probability measure that generates non-void random polytope
Let $C$ be a non-void compact convex set in $\mathbb{R}^d$, and $\nu$ a probability measure on $C$. Then under what conditions on $C$ and $\nu$, the following statement is true: If $X_1,\cdots,X_{d+1}$...
- 589
6
votes
1
answer
262
views
two-dimensional sections of polyhedral cones
Given a polyhedral cone, its intersection with any two-dimensional plane is either a polygon or a region enclosed by a polygonal curve. Is it a characterization of polyhedral cones? Does there exists ...
- 71
9
votes
0
answers
178
views
Is every planar point set the projection of vertices of a neighborly 4-polytope?
More exactly, written in coordinates, I'm curious to know if for every point set $(x_i,y_i)$ there are $(x_i,y_i,z_i,w_i)$ that are vertices of a neighborly polytope.
This problem comes from a simple ...
- 261
6
votes
0
answers
181
views
Looking for the correct version of a wrong statement from Barvinok's book on convex polyhedra
The book I'm concerned with is "Integer Points in Polyhedra" by A. Barvinok, which, I must say, is turning out to be highly fascinating.
A real finite-dimensional vector space $V$ defines the ...
- 3,493
1
vote
1
answer
179
views
What's the most efficient way to solve this euclidean projection on non-negative affine space constraint?
I've come across this convex optimization problem in my research where I need to project a matrix $X_0$ onto a non-negative affine space constraint and box constraints. Concretely,
$X \in \mathbb{R}^{...
- 13
2
votes
1
answer
261
views
Is mean width a Dehn invariant?
Let $P \subset \mathbf{R}^3$ be a convex polyhedron. Let $rP$ be the dilation of $P$ by the positive real number $r$.
The Dehn invariant of $P$ is an element of the weird real vector space $\mathbf{...
- 4,849
4
votes
1
answer
1k
views
Sampling point uniformly at random satisfying equality constraints
First of all, I apologize in advance if the question has already been asked in some way on this site and/or if there is a widely known solution to this problem.
The description of my problem is ...
- 143