Questions tagged [polytopes]
The polytopes 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 ...
