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

Filter by
Sorted by
Tagged with
1
vote
0answers
87 views

Integrality of polyhedra

Given two polyhedra in $H$ representation $P_1:Ax\leq b$ and $P_2:Bx\leq c$ which are integral are bounded when is their intersection also integral? Given two polyhedra in $H$ representation $P_1:Ax\...
2
votes
0answers
81 views

How to judge whether the following convex set contains a given point?

Let the set $\mathcal{S}=\left\{ \sum_{i=1}^n x_i\mathbf{h}_i:x_i\in[0,1] \text{ for all }i\right\}\subset\mathbb{R}^r$, i.e., a zonotope generated by $n$ column vector $\mathbf{h_1},\cdots,\mathbf{h}...
0
votes
0answers
21 views

Sectioning facets from Coxeter-Dynkin diagram

Terminology: a sectioning facet $Q$ of a $D$-dimensional polytope $P$ is another polytope which uses a $(D-1)$-dimensional subset of $P$’s vertices and edges and is maximal (it is not a diminishing of ...
2
votes
0answers
36 views

An easy way to recognize the edges of an orbit polytope?

Given a finite (orthogonal) matrix group $\Gamma\subseteq\mathrm O(\Bbb R^d)$ and a point $x\in\Bbb R^d$. The corresponding orbit polytope is $$\mathrm{Orb}(\Gamma,x):=\mathrm{conv}\{Tx\mid T\in \...
0
votes
0answers
59 views

Number of vertices in a polyhedron

Consider polytopes $$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$ $$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$ $$B[z_{1},z_{2},z]'\leq c$$ having vertex count $v_1,v_2$ and $v$ respectively. We ...
3
votes
0answers
23 views

Intrinsic definition of a cone in a normal fan

Let $P\subseteq \mathbb{R}^n$ be a full dimensional polytope. Let us assume that $P$ has a facet description with the following inequalities: $$ \left<x,u_F\right> \geq -a_F$$ where $u_F\in \...
1
vote
0answers
25 views

How to express a polytope by a matrix inequalty? [duplicate]

Consider a convex V-polytope generated by the origin and $n$ points $\mathbf{h}_1,\cdots,\mathbf{h}_n$ in $\mathbb{R}^r$. A Theorem in the area of convex geometry shows that each V-polytope is a H-...
2
votes
0answers
76 views

Is the projective symmetry group of a polytope more general than its linear symmetry group?

Give a (convex) polytope $P\subset\Bbb R^d$ (the convex hull of finitely many points). Consider its linear and projective symmetry groups: \begin{align} \DeclareMathOperator{\Aut}{Aut} \...
3
votes
0answers
45 views

Classifying/enumerating vertex-transitive simplicial polytopes

I'm interested in understanding the class of simplicial polytopes in $\mathbb R^n$ whose Euclidean isometry group $G$ acts transitively on the vertices. These are examples that I know of: simplicial ...
5
votes
1answer
100 views

A combinatorial characterization of the central inversion of a polytope?

Given a convex full-dimensional polytope $P\subset\Bbb R^d$ (convex hull of finitely many points and not contained in any proper affine subspace) and a symmetry thereof (a linear map $\smash{T\in\...
2
votes
3answers
234 views

Confining a polytope to one side of an affine hyperplane

Judging whether one convex polytope is inside of another when both are expressed as a system of linear inequalities seems not to be an easy problem. This answer on math.stackexchange.com claims the ...
4
votes
0answers
107 views

“Baues poset” of shellings of simplicial polytope?

Let me start with some background I want to use as analogy. Consider a (convex) polytope $P$ and its set of triangulations. Among all the triangulations, a well behaved subset are the regular ones: ...
8
votes
0answers
84 views

Can solutions to Thomson's problem have pentagons?

Thomson's problem asks for the minimum energy configuration for $N$ electrons on a sphere (refs: https://en.wikipedia.org/wiki/Thomson_problem, https://sites.google.com/site/adilmmughal/...
1
vote
0answers
45 views

Decomposition of Polyhedral - An example

There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system $$ \...
1
vote
1answer
79 views

Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]

Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...
6
votes
2answers
88 views

Partitions of convex planar regions into zonogons

A zonogon is a centrally symmetric convex polygon. Are there convex non-zonogons that can be partitioned into a finite number of (convex) zonogons? Same as 1 with the pieces allowed to be nonconvex ...
4
votes
1answer
166 views

Iterating projections to random halfspaces

Consider the following process: Start with a set $S = \mathbb R^n$. Repeat $L$ times: choose a random orthonormal basis $u_1, \ldots, u_n$, and consider the cone $C = \{ \sum \alpha_i u_i : \alpha_i \...
3
votes
0answers
66 views

Additional symmetries of the Traveling Salesman Polytope

Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...
2
votes
1answer
105 views

Anchor sets for lattice polygons: Part I

Suppose $V=\{(x_1,y_1), (x_2,y_2),\dots,(x_v,y_v)\}$ is a vertex set of lattice points satisfying $$0=x_1<x_2<\dots<x_v \qquad \text{and} \qquad y_1>y_2>\cdots>y_{v-1}>y_v=0.$$ ...
2
votes
1answer
60 views

Are zonotopes determined by their edge-graph?

General polytopes are not determined by their edge-graph (up to combinatorial equivalence). But I came accross the statement that zonotopes are determined in this way. Question: Is this true? And ...
3
votes
1answer
157 views

Cohomology ring of a hypersurface in toric variety

Let $X^n$ be a smooth projective toric variety corresponding to a simple polytope $P$. It is well known that the cohomology ring $H^*(X)$ can be described in terms of combinatorics of faces of $P$. ...
0
votes
1answer
64 views

If there are eigenvectors with largest components $i$ resp. $j$, then is there an eigenvector with two largest components $i$ and $j$?

Let $G=(V,E)$ be a connected (finite simple) graph with vertex set $V=\{1,...,n\}$ and let $\theta_2\in\Bbb R$ be the second-largest eigenvalue of its adjacency matrix. I wonder about the following ...
14
votes
2answers
304 views

Ehrhart period collapse for $123\ldots k$-avoiding Birkhoff polytope?

For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices $$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\ \pi_{2,1} & \ddots & \...
4
votes
2answers
114 views

Existence of a fundamental domain for the convex hull of group action on a rational polytope

Let $P \subset \mathbb R^n$ be a compact rational polytope (the affine space spanned by $P$ may not be $\mathbb R^n$). Let $G \subset {\bf GL}(n,\mathbb Z)$ be an arithmetic group. Let $$C = {\rm Conv}...
2
votes
1answer
75 views

State-of-the-art article on “uniform 5-polytopes?”

I would like to read article(s) that provide the “state of the art” on the following open problem: “Enumerate all convex uniform 5-polytopes.” This problem is posted on the “Open Problem Garden” (http:...
8
votes
1answer
180 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(\...
0
votes
0answers
35 views

Attached convex “hulls”

Let $\mathcal{P}$ a finite set of points of a Euclidean $\mathbb{E}^n$ and take the union $\mathrm{U}(\mathcal{P})$ of all closed half-spaces defined by $n$ elements of $\mathcal{P}$ that contain only ...
3
votes
1answer
168 views

What are midway sections of simplices?

This is a (slightly modified) crosspost. Subsequent edit - coordinates are changed to obtain simpler expressions; the existing answer is not affected. There is a family of convex polytopes: $P_n$ is $...
7
votes
2answers
119 views

Constructing a $0/1$ polytope from an abstract simplicial complex

Let us fix $\Delta$ a finite simplicial complex, and label the vertices of $\Delta$ as $\{1,2,\ldots,n\}$. For each $F\in \Delta$ let us consider the point in $\mathbb{R}^n$ given by: $$e_F := \sum_{i\...
2
votes
1answer
93 views

Minimum Euclidean squared norm in the convex hull of points with rational coordinates

This is probably known, but I have not located a reference. Let $P$ be the convex hull of $k$ points in $\mathbb R^n$ with rational coordinates. Consider the Euclidean square norm function $F:P\to\...
5
votes
1answer
140 views

Is there a polytope with an essentially unique shape?

More percisely: Question: Is there a (convex) polytope that has a unique realization up to, say, projective transformations? I suppose I have to assume that it has more than $d+2$ vertices/facets if ...
12
votes
1answer
702 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 ...
3
votes
2answers
132 views

If a polytope is centrally symmetric and combinatorially equivalent to a zonotope, is it a zonotope?

A zonotope is a polytope whose 2-faces are centrally symmetric. Question: If a polytope $P$ is centrally symmetric and combinatorially equivalent to a zonotope, is it itself a zonotope?
4
votes
2answers
173 views

Is there more than one pseudo-Catalan solid?

This question was asked on MSE a year ago. Motivation for this question can be found in other MSE questions here, here or here. Convex solids can have all sorts of symmetries: the platonic solids are ...
3
votes
1answer
264 views

An example in symplectic geometry

$\DeclareMathOperator\SU{SU}$Let $M$ be a coadjoint orbit of dimension 6 of $\SU(3)$, and let $T$ be the maximal torus in $\SU(3)$. If we denote $\mu : M \longrightarrow \mathbb{R}^2$ the moment map ...
3
votes
1answer
92 views

Maximal number of visible vertices

Let $P$ be a three-dimensional convex polytope with $N$ faces; $O$ a point outside $P$. What is the maximal number $f(N)$ of vertices of $P$ which may be seen from $O$?
3
votes
0answers
105 views

Edges in the convex hull of the union of random polygons

Let $P$ and $Q$ be two convex polygons in $\mathbb{R}^2$. Given $a > 0$, denote by $aP$ its image under the dilation by $a$ centered around the origin (i.e. the polygon obtained by replacing each ...
0
votes
0answers
33 views

Conditions on $a_i,b_i$ for $i =1,\ldots,n$, so that $\arg\max_{\|x\| \le 1}\min\{a_i^\top x + b_i\mid i = 1,\ldots,n\} \subseteq \{\|x\| < 1\}$

Let $A$ be an $n \times m$ matrix with rows $ a_1,\dots,a_n \in \mathbb R^m$ and let $b=(b_1,\dots,b_n)$ be a vector in $\mathbb R^n$. Let $\mathbb B_m$ be the centered closed unit-ball in $\mathbb R^...
0
votes
1answer
95 views

If $C_1\subseteq C_2$ are two closed convex cones that are pointed with $\partial C_1\subseteq \partial C_2$ then is $C_1=C_2$?

Let $C_1$ and $C_2$ be two proper full dimensional closed convex cones in $\mathbb{R}^n$ that are pointed. Suppose that $C_1\subseteq C_2$ and that the boundary of $C_1$ is contained in the boundary ...
4
votes
1answer
62 views

Mass distributions for high dimensional simplex and cross polytope

In this question, it is shown that the radial mass distribution of an $n$-cube (i.e. the probability density for the distance from a point selected uniformly from within an $n$-cube to the cube's ...
1
vote
1answer
96 views

Exact volume calculation of a polytope is NP hard under which restrictions?

Computing the exact volume of a polytope given in half space representation seems to be NP-hard. One paper I found proved it is hard for rational coefficients. (However, the paper itself was behind a ...
3
votes
0answers
53 views

How to find the dimension of the polar cone of a convex cone generated by some given vectors

Suppose we have access to a generating set $\{v_1, ..., v_k\}\subseteq\mathbb{R}^n$ of the convex cone $C=cone(v_1, ..., v_k)$, where $cone(\cdot)$ is the conical hull (i.e. nonnegative span) of ...
9
votes
0answers
160 views

How to correctly state Cauchy's rigidity theorem?

Cauchy's rigidity theorem is usually cites briefly as Any two (convex, 3-dimensional) polyhedra with pairwise congruent faces are themselves congruent. As a more formal generalization to general ...
5
votes
0answers
60 views

Which polytopes can be deformed while keeping their edge-lengths?

Let $P\subset\Bbb R^d$ be a convex polytope (a convex hull of finitely many points). Lets call it flexible, if it can be continuously deformed while keeping its combinatorial type, and keeping its ...
2
votes
1answer
53 views

Is there a non-orthogonal linear deformation of a polytope that preserves edge-lengths and vertex-origin-distances?

Is there a polytope $P\subset\Bbb R^d$ (convex hull of finitely many points, not contained in a proper affine subspace), and a linear, but non-orthogonal transformation $T\in\mathrm{GL}(\Bbb R^d)\...
5
votes
0answers
112 views

How does a map from permutahedra to associahedra factor through multiplihedra?

Let $P_i$ denote permutahedra, $K_i$ associahedra and $J_i$ multiplihedra. In their famous paper on operadic diagonals, Saneblidze and Umble use a projection $p_i: P_i \to K_{i+1}$ which factors as $...
9
votes
2answers
193 views

Integer decomposition property with a partial order

Let $\mathcal{P}$ be a convex lattice polytope in $\mathbb{R}^n$. We say that $\mathcal{P}$ has the integer decomposition property (or "is IDP") if for all $k\in \mathbb{N}$ and $\alpha \in ...
3
votes
1answer
80 views

Solid angles at points in an orthosimplex

Given a point ${\bf x} = (x_1,x_2,\dots,x_n)$ in the orthosimplex $K = \{(x_1,x_2,\dots,x_n)\ : \ 0 \leq x_1 \leq x_2 \leq \dots \leq x_n \leq 1\}$, what proportion of a ball of radius $\epsilon$ ...
16
votes
1answer
592 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 ...
0
votes
0answers
29 views

Distance to the “boundary” of a polyhedral complex

Suppose I have a polyhedral complex $\{P_1, \ldots, P_k\}$ and let $S := \cup_{i = 1}^k P_i$. I am interested in a function which measures the distance from a point $x \in S$ to the "boundary&...

1
2 3 4 5
16