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
942 questions
5
votes
1
answer
384
views
Examples of Polyhedra with Large Shadows
Let $P \subseteq \mathbb{R}^n$ be a polyhedron described by $\mathcal{O}(n^{c_1})$ inequalities, where $c_1$ is a constant. Moreover, let $M\colon P \to \mathbb{R}^2$ be a linear mapping. I'm looking ...
9
votes
2
answers
153
views
Generate polyhedra by collapsing vertices of a polyhedron
I am looking for basic information about the following idea:
(I) Consider a square. By collapsing two adjacent vertices, we obtain a triangle.
(II) Consider a three-dimensional cube. By collapsing a ...
5
votes
0
answers
233
views
Is there a well-established terminology for polyhedra/polytopes?
I got confused lately. It seems like in the metric context a polyhedron tends to mean an intersection of a finite number of half-spaces, while a polytope is a convex hull of a finite set of points. At ...
8
votes
0
answers
6k
views
Convex hulls of compact sets
Let $A$ be a compact set in a separable Hilbert space $H$, and let $\bar A$ denote its convex hull. Is $\bar A$ compact?
3
votes
1
answer
153
views
Taking powers of polytopes
I am not sure this is a well framed question but I would like to know if anything like "taking the power" of a polytope is known.
Imagine this situation where I want to think of such a thing : say ...
15
votes
1
answer
640
views
Smallest regular simplex containing the unit cube in $R^n$
What is the length $e_n$ of the edge of the smallest $n$-dimensional regular simplex $S_n$ containing the $n$-dimensional unit cube $Q_n$?
In particular, is there $n$ such that $e_n<\sqrt{2}(n+1-\...
2
votes
1
answer
433
views
intersection of the unit cube and a hyperplane containing the main diagonal
Let $A$ be a linear $m$-dimensional subspace of $\mathbf{R}^n$ $m < n$, containing the point $(1,1,\ldots,1) \in \mathbf{R}^n$,
and consider the intersection of $A$ and the unit cube $\Delta_n$ (...
9
votes
1
answer
665
views
Question about tetrahedron decomposition
Are there tetrahedra which can be subdivided into three non-overlapping parts similar to the original? I believe this would require splitting one face into three parts. I know some types of tetrahedra ...
5
votes
2
answers
563
views
Covering convex polygons with inscribed disks
The following problem came up when discussing mapping software (e.g., Google maps) with computer scientists. By $B(c,r)$ I mean the planar disk (open or closed, it doesn't matter) of radius $r$ around ...
0
votes
1
answer
201
views
Recursive linear programming on a linear subset of a simplex
The problem I am working on is:
Given an $n$ dimensional vector $r \in \mathcal{R}^n$, and a convex set $G=\{\mu \in \mathcal{R}^n | \mu_i \ge 0, ~ \mu^T \mathbf{1}=1, ~ A\mu =0 \}$ where $\mathbf{1}...
16
votes
2
answers
536
views
What is $A+A^T$ when $A$ is row-stochastic ?
This is motivated by this MO question.
If $A\in{\bf M}_n({\mathbb R})$ is row-stochastic (entrywise non-negative, and $\sum_j a_{ij}=1$ for all $i$), then $M:=A+A^T$ is
symmetric,
entrywise non-...
7
votes
1
answer
248
views
Sample integer points of cross-polytope uniformly
For $r,d\in\mathbb{N}$, let
$$C_{r,d}=\{x\in\mathbb{Z}^d: \|x\|_1\le r\}\subset\mathbb{Z}^d$$
be the set of integer points of the $d$-dimensional cross-polytope with radius $r$.
What is (...
4
votes
0
answers
124
views
Reference for this fact about perturbed polytopes?
Let $K \subset \mathbb{R}^n$ be a polytope (i.e., an intersection of finitely many halfspaces that has finite volume) and consider $F(K) := \int_K \|x\|^2\, {\rm d}x$, where $\|\cdot\|$ is the ...
4
votes
1
answer
969
views
Simplex in convex polytope, pulling triangulation
Let $P$ be a convex $d$-dimensional polytope.
I have two questions, related to triangulations of $P$.
Question 1:
Let $p$ be in the interior of $P$. Can I always find a triangulation of $P$,
such ...
6
votes
2
answers
3k
views
Finding the convex combination of vertices which yields an inner point of a polytope
Given a convex polytope $P\in \mathbb{R}^n$, and a point $x\in P$, Caratheodory's theorem gives us that there exists a set of at most $n+1$ vertices of $P$, such that $x$ is a convex combination of ...
2
votes
1
answer
265
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{...
1
vote
0
answers
196
views
Facet Enumeration Problem nondegeneracy case
Hello in case of a nondegeneracy case of the Facet Enumeration Problem, there is a polynomial algorithm for the convex hull problem as written here https://www.inf.ethz.ch/personal/fukudak/polyfaq/...
1
vote
0
answers
368
views
Convex hull of the intersection of nonconvex sets
I have a set $D$ in $\mathbb{R}^{d+1}$ which is the intersection of $d$ domains $D_i$ given by $f(x_{i}) \leq x_{i+1} \leq g(x_{i})$ for two functions $f$ and $g$.
I want to find the convex hull of $...
1
vote
0
answers
47
views
What separates a cyclic polytope from a projective polytope?
I am having trouble understanding the difference between a cyclic polytope and a convex projective polytope as positive geometries.
The link https://arxiv.org/pdf/1703.04541.pdf is the source of ...
2
votes
0
answers
165
views
Link of a power series by the Bernoullis for a Riccati equation to zonotopes?
On pg. 85 of The Rise and Development of Theory of Series up to the Early 1820s by Ferraro is a series soln. of
$$ d^2z/z = -x^2dx^2 $$
related to the reputed first appearance of a Riccati-type eqn.,...
3
votes
1
answer
151
views
The center of a minimal convex superbody
Is the following true?
CONJECTURE: $\,$ Let $\ B\ C\subseteq\mathbb R^n\ $ be convex bodies in $\mathbb R^n$ such that $\ C\ $ is centrally symmetric, $\ B\subseteq C,\ $ and $\ t\!\cdot\! B\ $ cannot ...
2
votes
1
answer
113
views
Internal edges in Convex Polytopes
Suppose $S\subset{\mathbb R}^n$ is an infinite subset that is in general position which means that the intersection of $S$ with every affine subspace of dimension $d<n$ always contains at most $(d+...
1
vote
0
answers
53
views
Projecting two convex polyhedra onto their intersection
Suppose we are given two convex polyhedra $\mathcal{C}_1, \mathcal{C}_2 \subset \mathbb{R}^n$ with non-empty intersection $\mathcal{C}_1 \cap \mathcal{C}_2 \neq \emptyset$.
For the orthogonal ...
14
votes
0
answers
479
views
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?
After reading these very interesting questions, I came up with another one:
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...
20
votes
1
answer
591
views
Update to Shephard's "Twenty Problems on Convex Polyhedra"
Forty-three years ago, Geoffrey Shephard published an influential list of open problems
on convex polyhedra.
Progress has been made on several of his problems, and perhaps some have been completely ...
1
vote
1
answer
391
views
Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces
Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by
$$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$
$$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$
I wish to find their convex hull, that is a ...
7
votes
1
answer
824
views
Ehrhart polynomial
What is the Ehrhart polynomial of the regular cross-polytope of dimension d? Are there published upper and lower estimates?
2
votes
1
answer
248
views
Choosing the weights of a Voronoi diagram -- is this function always the gradient of another function?
This question is related to the earlier question Weighted area of a Voronoi cell . As in that question, let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,...
3
votes
0
answers
387
views
regular triangulations of the product of two simplices
Is description of all regular triangluations of $\Delta^n\times \Delta^k$ known? (Regular triangulations are those which correspond to vertices of Gelfand--Kapranov--Zelevinsky secondary polytope, or, ...
6
votes
1
answer
587
views
Study of convex polytopes via commutative algebra
Let $P \subset \mathbb{R}^d$ be any convex polytope with integral vertices, and let $M$ be the additive submonoid of $\mathbb{R}^{d+1}$ which is generated by $\{ (v,1) : v \in P \cap \mathbb{Z}^d \}$. ...
6
votes
1
answer
237
views
Some polytopes in $\mathbb R^n$ whose vertices have coordinates 1, -1 or 0
Let $n$ and $k$ be positive integers with $k\leq n$.
Let $P(n,k)$ be the convex hull in $\mathbb R^n$ of the $2^k {n \choose k}$ vectors whose exactly $k$ coordinates belong to $\{\pm 1\}$ all the ...
3
votes
1
answer
445
views
Dehn-Sommerville relations for $\Delta$-complexes
Let $M$ be a closed, triangulated manifold of dimension $m$ and $K(M)$ be its triangulation. Let $f_i$ denote the number of $i$-simplices of $K(M)$. As proved by Klee the face numbers satisfy the ...
14
votes
0
answers
254
views
Is combinatorial automorphism of symmetric convex polytope always antipodal?
The question is formulated in the title. More precisely, if $P$ is an origin-symmetric convex polytope in $\mathbb{R}^d$, and $f$ is a bijective transform of the set of the vertices of $P$, which ...
2
votes
0
answers
41
views
Efficient $H$ representation of matrices with distinct cyclic shift permuted entries
Given points $v_1,\dots,v_n\in\mathbb Z^n$ in codimesion $1$ hyperplane $x_1+\dots+x_n=t$ with $0\leq x_{i}$ and a cyclic shift permutation $\sigma$ where
$v_1,\dots,v_n$ when written as columns of ...
6
votes
0
answers
491
views
Minimum solid angle and aspect ratio of an $n$-simplex
In computational geometry and other fields, it is of interest to have degeneracy measures for shapes of simplices, which quantitatively seperate the regular simplex from degenerate simplices.
In two ...
13
votes
1
answer
1k
views
When is a matrix similar to a non-negative matrix?
Consider a real square matrix $A$ of size $n\times n$. Under which conditions on $A$ does there exist a row-stochastic matrix $U$ (non-negative, rowsums = 1), such that $A'=U^{-1}AU$ is a non-negative ...
4
votes
2
answers
191
views
Affine hull of a set of non-negative matrices with fixed row-sums
Fix any non-negative matrix $M \in \mathbb{R}_{\geq 0}^{m \times n}$ that contains no zero-row and no zero-column.
Further, fix any positive vector $r \in \mathbb{R}_{> 0}^m$.
With $nz(M) := \{(i,j)...
1
vote
0
answers
57
views
geometry of intersection of 2 polytope in higher dimension [closed]
Suppose $P_{1}$ is a $\frac{n}{2}$-dimension polytope in $ R^{n}$ with barycenter $c$, and $P_{2}$ is a $(n-1)$-simplex in $R^{n}$ with the same barycenter as $P_{1}$, i.e $c$ . And also suppose they ...
4
votes
2
answers
250
views
Build a topological polytope with a specified CW-structure
I am a topologist and not quite familiar with the tools for building a polytope. I would like to build some topological polytope which is an somewhere in between permutohedron and associahedron which ...
3
votes
1
answer
396
views
Lattice points in cross-polytopes
Let $E\subset \mathbb{R}^n$ be a cross-polytope:
$$E= \left\lbrace x : \frac{|x_1|}{q_1}+\cdots+\frac{|x_n|}{q_n}\leq 1 \right\rbrace, $$
where $q_1,\dots,q_n$ are positive integers. I am interested ...
4
votes
2
answers
567
views
Realization spaces for regular convex polytopes
Q1.
Are there convex polytopes combinatorially equivalent to each of the regular polytopes
that are realized with integer vertex coordinates?
&...
2
votes
2
answers
330
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. ...
4
votes
0
answers
2k
views
Regular cross-sections of a dodecahedron; analogous sections of 4-polytopes
One can intersect a dodecahedron with a plane and
obtain an equilateral triangle, a square, a regular pentagon,
a regular hexagon, and a regular decagon:
&...
2
votes
1
answer
194
views
Approximating Ehrhart Polynomial of Rational n-Tetrahedron
A set of positive integers $d_1, \dots, d_n$ describe a n-dimensional tetrahedron $T$ with the vertices
$$ (0,\dots,0), (1/d_1,0,\dots,0), (0, 1/d_2,\dots,0), \dots, (0,\dots,1/d_n).$$
Let $L_T(t)$ be ...
6
votes
1
answer
393
views
Recovering a polyhedron from its tumble-density profile
Imagine a white convex polyhedron $P$ tumbling randomly about its fixed center of gravity (c.g.)
$c$ against a blue background.
A long-exposure photo would show pure white in a neighborhood of $c$
(...
1
vote
1
answer
77
views
Uniqueness of polytope embedding from symmetry group
Do the symmetry group generators of a regular convex polytope and a marked $\{0,1\}^n$ vertex point suffice to embed the polytope uniquely with $\{0,1\}^n$ vertex set?
If so can we find the John's ...
1
vote
0
answers
243
views
16-cell honeycomb (4D tiling by cross-polytopes)
A 4-dimensional cross-polytope (also called 16-cell) is a regular polytope whose vertices are all permutations of $(\pm1,0,0,0)$. It is known that this body tiles the space $\mathbb{R}^4$ by ...
6
votes
0
answers
434
views
Algorithm to express a point from a H-polyhedron as convex combination of extreme points
Let $P\subset\mathbb{R}^n$ be a convex polyhedron described as an intersection of hyperspaces, that is,
$$P:=\{\boldsymbol{x}: A\boldsymbol{x} \leq \boldsymbol{b}\}$$
Let $\boldsymbol{x} \in P$. We ...
4
votes
1
answer
694
views
$\mathcal{H}$-polyhedron under a linear map
Let $P = \{ x \in \mathbb{R}^n \mid Ax \leq b \}$ be a (bounded) polyhedron for $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$, $n,m > 0$.
Moreover, let $M \colon \mathbb{R}^n \to \...
3
votes
0
answers
219
views
First to note/document the relation between permutohedra and multiplicative inversion
The relation between the refined face numbers of the permutohedra and the formal series expansion of the reciprocal of a function (exponential generating function, formal Taylor series) is given in ...