Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [polytopes]

The tag has no usage guidance.

4
votes
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
3answers
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
3answers
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
1answer
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 ...