# Questions tagged [polytopes]

The polytopes tag has no usage guidance.

**4**

votes

**0**answers

76 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**

vote

**0**answers

19 views

### Covering a simplex efficiently by efficiently describable polytopes?

Take a standard simplex or cube in $\mathbb R^n$.
Is there a way to cover it with $O(poly(\log n))$ convex polytopes each describable by only $O(poly(\log n))$ half-plane inequalities?
If not what ...

**1**

vote

**0**answers

111 views

### Is there a method to cut a hypercube into disjoint cubes [closed]

Since Borsuk conjecture hold for centrally symmetric convex sets in $\mathbb{R}^n$
so we can cut a hypercube into at least $n+1$ disjoint parts.
Is there a method how can one do that?

**0**

votes

**1**answer

71 views

### Projections of particular simplex yielding boundary of a regular polygon?

What is the maximum $m$ such that there is a simplex with $n$ vertex points in $n-1$ dimensions whose projection yields boundary of a regular $m$-gon on $2D$ plane?

**6**

votes

**0**answers

80 views

### Tiling with Horn's polytopes

Let $n\ge2$ be an integer. Consider the hyperplane $H_n$ of ${\mathbb R}^n$ defined by the equation $x_1+\cdots+x_n=0$ and then the sector $P_n\subset H_n$ defined by the inequalities $x_1\le\cdots\le ...

**1**

vote

**0**answers

28 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

37 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 ...

**3**

votes

**1**answer

708 views

### What does it mean polynomials share Newton polytope?

I have trouble understanding the connection between polynomials and Newton polytopes. I will try to make a short introduction to my problem and hope you will catch on. In the end I will ask questions.
...

**6**

votes

**2**answers

147 views

### “Totally transitive” polytopes which are not regular

Is it possible to have an abstract polytope which is vertex-transitive, edge-transitive, face-transitive, etc. (individually transitive on faces of each particular dimension) and yet not flag-...

**4**

votes

**0**answers

77 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 ...

**6**

votes

**1**answer

1k views

### Approximation of convex hull in high dimension

What are efficient methods (polytime) to compute an approximation of the convex hull in high dimension (say, $30000$) for a given set of points?
Edit:
I am looking for an algorithm for getting the ...

**1**

vote

**1**answer

87 views

### Derive a vertex representation of a permutohedron from its linear-inequalities form

Let us define the $n$-permutohedron $P_n$ as the set of all $x\in\mathbb{Q}^n$ such that
$$\sum_{i=1}^n x_i = \binom{n{+}1}{2}\ \ \ \land\ \ \ \forall\,\text{nonempty}\ S\subsetneq\mathbb{N}_n\colon\ ...

**1**

vote

**0**answers

38 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. ...

**1**

vote

**0**answers

77 views

### Existence of polytope

Does there exist a polytope in dimensional d consisting of $k>d+1$ faces satisfying that every d faces intersect? I tried 3 dimensional cases, and it seems negative. But is it all negative for any ...

**3**

votes

**0**answers

531 views

### Testing if a point is inside a convex polytope formed by halfspaces in n-dimension

Assume we have a convex polytope that is formed by the intersection of $k$-halfspaces in $\mathbb{R}^{n}$.
$$
a_{0,0}x^{n-1} + {a}_{0,1}x^{n-2} + ... a_{0,n-1} \leq 0
$$
$$
a_{1,0}x^{n-1} + {a}_{1,...

**2**

votes

**1**answer

235 views

### Digital topology, animal problem, 2-sphere and torus

I have the following question relating digital topology, surfaces, particularly $S^2$ and torus.
Can a body $B$ constructed with cubes (without cavities or tunnels) and with frontier homeomorphic to ...

**11**

votes

**1**answer

336 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$...

**1**

vote

**1**answer

184 views

### Linear map of Zonotopes [closed]

Consider a linear system with a map $A: \mathbb{R}^n \rightarrow
\mathbb{R}^m$ such that $y = A x$ with $n \geq m$
The input space $x$ is constrained by a zonotope set $\mathcal{X}
\subseteq \mathbb{...

**4**

votes

**2**answers

203 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 ...

**2**

votes

**1**answer

114 views

### Volume of a polytope with relaxed constraints

Consider a polytope in $n$ dimensions defined by a set of linear constraints:
$$P = \{x \in \mathbb{R}^n : Ax \leq b\}$$
where A is some $m \times n$ constraint matrix, and $b = (b_1,\ldots,b_m)$ is ...

**1**

vote

**0**answers

80 views

### Does the set of points minimizing their distance to a multiset of convex polytopes result in a polytope?

Let $\mathbb{R}^n$ be a normed affine space of finite dimension $n$, and $d : \mathbb{R}^n \times \mathbb{R}^n \mapsto \mathbb{R}^+$ be the distance derived from the norm under consideration. A convex ...

**2**

votes

**0**answers

193 views

### Polytopes generated as the convex hull of the orbit of a finite reflection group acting on a given vector

Consider a finite reflection group acting on $\mathbb{R}^N$. Pick a vector $x \in \mathbb{R}^N$ and look at the convex hull of its orbit. This is a polytope.
There are some interesting particular ...

**5**

votes

**1**answer

507 views

### Generalized permutahedron and random polytopes

The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the ...

**8**

votes

**1**answer

145 views

### Labeled polytopes

In a "problem of a week" contest in my school, I gave the following problem to students: we assign to each vertex of a cube a number $1$ or $-1$. And we associate to each face the product of the ...

**2**

votes

**1**answer

136 views

### Estimates on the number of vertices of reflexive polytopes

Suppose $M \cong \mathbb{Z}^n$ is a rank $n$ lattice, with dual lattice $N$. Suppose $\Delta$ is a full dimensional lattice polytope (i.e. convex hull of finite lattice points) in $M$. Then $\Delta$ ...

**17**

votes

**1**answer

712 views

### An NP-hard $n$ fold integral

We are given rational numbers $[c_1, c_2, \ldots, c_n]$ and $v$ from the interval $[0,1]$.
Consider the $n$-fold integral
$$
J = \int_{\theta_1 \in I_1, \theta_2 \in I_2 \ldots, \theta_n \in I_n} d\...

**2**

votes

**1**answer

1k 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| \, \...

**7**

votes

**1**answer

403 views

### Does every simplicial polytope have a topology-preserving contractible edge?

An edge of a triangulated manifold is said to be contractible if it may be contracted to a vertex without modifying the topological type of the underlying manifold. Otherwise, the edge is ...

**5**

votes

**3**answers

645 views

### Who knows this convex polytope?

I hope this is not too trivial for this forum. I was wondering if someone has come across this polytope.
You start with the rhombic dodecahedron, subdivide it into four parallellepipeds,
and then ...

**3**

votes

**1**answer

359 views

### moduli space of polytopes

When considering classification problems about polytopes, I sometimes has the feeling that one need to talk about certain parametrized families, i.e. moduli space of such polytopes. But neither do I ...

**3**

votes

**1**answer

220 views

### Classification of lattice polytopes with small number of lattice points in the facets

Suppose $P$ is a convex lattice polytope in $Z^3$ without interior lattice points, and we require the interior lattice points of each facet(i.e. dimensional 2 faces) are neither too much nor too few, ...

**9**

votes

**2**answers

1k 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 ...

**5**

votes

**1**answer

378 views

### What can be said about number-theoretic properties of the solid angle measures of polytopal cones in the weight lattice of sl(n)?

The following question might be elementary — it is too far from my area of expertise to tell. It has shown up in my research in an interesting way, which I will not go into here, but I'm happy to ...

**9**

votes

**1**answer

567 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 ...

**3**

votes

**0**answers

294 views

### Sampling from a partition of a hypercube by convex polytopes.

I have a binary space partitioning (BSP) tree which recursively partitions a hypercube using linear hyperplanes. That is, a hyperplane splits the hybercube in half, creating two convex polytopes. Each ...

**3**

votes

**0**answers

253 views

### Polygon illumination with perturbed reflections

Here is a variation on the classical polygon illumination problem. For $c \geq 0$ we say that a mirror has reflection index $c$ if whenever a ray hits the mirror with angle of incidence $\alpha$ then ...

**3**

votes

**1**answer

221 views

### Non-inherited symmetries of shadows of point sets

Sometimes a point set in Euclidean space may have a shadow with an unexpected symmetry. The purpose here is to ask when this happens or when it doesn't happen (in some generality).
This requires a ...

**2**

votes

**3**answers

914 views

### An exterior angle theorem for n-dimensional polytopes?

In the plane, the exterior angle of a vertex is $\pi -$ the standard ("interior") angle, which may be negative in some cases. The following is true for non-weird polygons:
The sum of the exterior ...

**9**

votes

**1**answer

834 views

### Spanning polytopes

Hamiltonian cycles (seen as spanning polygons) are interesting for several reasons (only a few of which I am aware of), but especially because not every connected graph has a Hamiltonian cycle (is ...