Stack Exchange Network

Stack Exchange network consists of 174 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 [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

1
vote
0answers
35 views

Volume of caps of a polytope

Let $K$ be a polytope in $\mathbb R^d$, blow it up by a factor $\lambda>0$. For a unit vector $u \in \mathbb S^{d-1}$, $\lambda K$ has 2 support hyperplanes $H_1$ and $H_2$ with corresponding ...
4
votes
1answer
75 views

Regularity of John's ellipsoid

Consider a finite dimensional real Banach space $E$, with norm say $|\cdot|$. Let $N$ denote the set of all norms on $E$. Suppose that $\varphi_1, \varphi_2 \in N$ have unit balls $B_1$ and $B_2$, ...
1
vote
0answers
26 views

Compute the edge-skeleton of a polytope given by its vertices

Let $P$ be a polytope given by a vertex description, i.e., $P=conv(\{x_1,\ldots,x_m\})\subset\mathbb{R}^n$. Is there an efficient (i.e., not relying on Linear Programming) algorithm to compute the ...
4
votes
1answer
92 views

What is the lower bound for the number of facets that a general convex $d$-polytope with $n$ vertices can have?

I am familiar with Barnette's Lower Bound Theorem on the number of facets a $d$-dimensional simplicial convex polytope with $n$ vertices can have. Is there a similar result for a general (i.e. not ...
0
votes
1answer
69 views

Closed form solutions for maximal subsets of convex polytopes

I'm looking for any known exact results about inscribing simple convex bodies inside a convex polytope. The most famous is the Löwner-John ellipsoid, but as far as I understood in general there is no ...
-1
votes
1answer
37 views

Characterisation of a superset of the simplex

Does there exist a nice description of the following set: \begin{equation} A:=\left\lbrace x\in\mathbb{R}^{n}\ \colon\ 0< x_{i}-\bar{x}+\frac{1}{n}< 1\ \text{for} \ i=1,\dots,n\right\rbrace, \...
2
votes
0answers
33 views

An implementation of Minkowski reconstruction in 3 dimensions

By a theorem of Minkowski from 1903, an $n$-dimensional polytope $P\subset \mathbb R^n$ is determined up to translation by its unit face normal $u_1,\dots,u_k\in S^{n-1}$ and the corresponding $(n-1)$ ...
0
votes
0answers
33 views

When is the set of faces of a convex polytope algebraically independent?

This is related to another question of mine Let $V=\Bbb R^n$. Morelli defined the (commutative unital) ring $L(V)$ to be the additive group generated by the indicator functions of convex polytopes in ...
3
votes
0answers
67 views

The ring generated by a convex polytope and its faces

Let $V=\Bbb R^n$. Morelli defined the (commutative unital) ring $L(V)$ to be the additive group generated by the indicator functions of convex polytopes in $V$ with multiplication induced by Minkowski ...
1
vote
1answer
60 views

Linear relations between volume of a polytope and its faces

Let $P$ be a polytope. Is anything known about the set of linear relations that hold between the volumes of the (not-necessarily proper) faces of $P$ as $P$ “varies slightly”? By varies slightly I ...
2
votes
1answer
101 views

Polygon of convex arcs

Convex polygons in the plane $R^2$ arise in linear programming where the constraints are linear. The objective linear function attains its maximum at a vertex of the feasible region(if exists). Assume ...
3
votes
1answer
128 views

Minkowski sum of polytopes from their facet normals and volumes

By Minkowski's work in the early 1900s, every polytope $P\subset\mathbb R^n$ is determined up to translation by its unit facet normals $u_1,\dots,u_k$ and facet volumes $\alpha_1,\dots,\alpha_k$. ...
1
vote
0answers
33 views

Possible volumes of lattice polytopes

All polytopes here are assumed to be convex lattice polytopes. Given a polytope $P$, set $$v(P):= (\operatorname{vol}(F))_{F\text{ a face of }P},$$ where the volume of a $d$-dimensional polytope $P\...
10
votes
2answers
155 views

The set of polytopes with given $f$-vector

Let $f=(f_0,\ldots f_n)$ be a vector in $\Bbb N^{n+1}$. Let $X$ be the set of all (ordered) $f_0$-tuples in $\Bbb R^n$ whose convex hull has $f$ as its $f$-vector. Assume that $X$ is non-empty. Is ...
0
votes
0answers
22 views

Projecting a polyhedral cone onto its intersection with the infinity-norm ball

For a point in a convex polyhedral cone, $x\in \mathcal{C} = \{\sum_{i=1}^m \alpha_i r_i \vert \alpha_i \geq 0, r_i \in \mathbb{R}^n \}$, is there an efficient algorithm to project $x$ onto the ...
6
votes
0answers
76 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 ...
3
votes
3answers
173 views

What is the probability distribution of the $k$th largest coordinate chosen over a simplex?

Suppose we're selecting points uniformly at random from the $N$-simplex $S_N = \{x \in \mathbb R^{N+1}: $ all $ x_i \ge 0$ and $x_1 + \ldots x_N = 1\}$. One way to do this in practice is choose $N-...
2
votes
0answers
22 views

condition on rational polyhedral cone to guarantee dual cone is homogeneous

Let $\sigma\subseteq \Bbb R^d$ be a full-dimensional rational polyhedral cone which is strongly convex (i.e. $\sigma\cap-\sigma=0$). Definition. The cone $\sigma$ is homogeneous if there are ...
13
votes
1answer
274 views

Can the graph of a symmetric polytope have more symmetries than the polytope itself?

I consider convex polytopes $P\subseteq\Bbb R^d$ (convex hull of finitely many points) which are arc-transitive, i.e. where the automorphism group acts transitively on the 1-flags (incident vertex-...
2
votes
0answers
98 views

Can computers take uniform samples from a polytope?

For each $r \in \mathbb N $ write $\mathbb Z/ 10^r = \{a/10^r: a \in \mathbb Z\}$ and $P(r)$ for the lattice $(\mathbb Z/10^r)^N \subset \mathbb R^N$. Suppose the plane $P \subset \mathbb R^N$ is ...
3
votes
1answer
61 views

Maximal edge length of symmetric polytopes

For me, a polytope is the convex hull of finitely many points. It is said to be vertex-transitive / edge-transitive if its symmetry group acts transitively on its vertices / edges. Let's call a ...
2
votes
1answer
61 views

Separation of two pointed polyhedral cones using hyperplanes generated by facets

Let $C_1$ and $C_2$ two pointed (that is, with vertex in $0$) polyhedral cones in $\mathbb{R}^n$ with $\dim(C_1)=\dim(C_2)=n$. If $$\mbox{relative interior}(C_1)\cap \mbox{relative interior}(C_2)=\...
4
votes
1answer
318 views

Mathematical Structure and Objects Induced by Pairs of Disjoint Subsets

Let $\mathcal{S}$ be a finite, discrete and non-empty set, i.e., $$\begin{align} \operatorname{card}\left(\mathcal{S}\right) & =:n\in\mathbb{N}^+\\ V& :=\{v\subset\mathcal{S}\ |\ v\ne\...
4
votes
2answers
234 views

Fast projection onto a subspace

Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{...
1
vote
0answers
47 views

Can projecting a simplex onto orthogonal subspaces exposes the same vertices and edges?

Given the regular $n$-dimensional simplex $S\subset\Bbb R^n$ with $n\ge 4$, as well as two orthogonal subspaces $V,W\subset\Bbb R^n$ of dimension $\ge2$ (not necessarily of same dimension, not ...
5
votes
1answer
192 views

Can two non-equivalent polytopes of same dimension have the same graph?

By a polytope I mean the convex hull of finitely many points. The graph of a polytope is the graph isomorphic to its 1-skeleton. By equivalence of polytopes I mean combinatorial equivalence, i.e. ...
5
votes
2answers
233 views

Is every polytope combinatorially equivalent to the intersection of a simplex and a linear subspace?

I wonder whether such a result is known, and if so, whether the proof is trivial. By polytope I mean the convex hull of finitely many points in $\Bbb R^n$. Assume the simplex to be symmetric and ...
1
vote
0answers
30 views

How to minimize n-polytope's bounding box with linear transformation?

I am working on an exact algorithm for integer linear programming for my master's thesis: $Ax\leq b, x \in \mathbb{Z}^n$ $cx\rightarrow min$ For my idea to work out, I need a guarantee that n-...
15
votes
3answers
430 views

Can we realize a graph as the skeleton of a polytope that has the same symmetries?

Given a graph $G$, a realization of $G$ as a polytope is a convex polytope $P\subseteq \Bbb R^n$ with $G$ as its 1-skeleton. A realization $P\subseteq \Bbb R^n$ is said to realize the symmetries of $...
0
votes
0answers
58 views

Applying a piecewise linear function to vertices of a polytope while remaining in facet representation

Let $P \subseteq \mathbb{R}^d$ be a polytope with vertices $V$, and let $f : \mathbb{R}^d \to \mathbb{R}$ be a function. Let $P' \subseteq \mathbb{R}^{d+1}$ be the polytope with vertices $\{(v, f(v)) \...
2
votes
0answers
35 views

2-dimensional smooth lattice polytopes with minimal edge lengths

For each integer $k \geq 3$, does there exist a full-dimensional, $2$-dimensional, smooth lattice polytope $P$ with $k$ edges, such that each edge contains only two lattice points (i.e. only its ...
1
vote
0answers
69 views

Simple polytope with smooth facets

Let $P$ be a simple $3$-dimensional (and full-dimensional) lattice polytope such that every facet $F$ is a smooth polytope. Is then $P$ itself smooth? EDIT: A full-dimensional lattice polytope $P$ is ...
1
vote
0answers
55 views

Can sufficiently symmetric polytopes be uniquely reconstructed from their 1-skeleton?

General convex polytopes can not be uniquely reconstructed from their 1-skeleton1, as explained here. Not even the dimension is known from the skeleton, as e.g. the complete graph $K_n,n\ge 5$ is the ...
4
votes
1answer
142 views

Is the preimage of a face under an affine map a face?

Let $X\subseteq\mathbb{R}^n$ be a convex set. Let $\pi{:}\ X\to\mathbb{R}^m$ be a linear map, with $m<n$ (for example, a projection). Let $\pi^{-1}(y)=\{x\in X\mid\pi(x)=y\}$ denote the inverse of $...
0
votes
0answers
28 views

Interpretation of this sum for concave bodies

For some polyhedron, $P$, define $$H(P)=\sum_{e\in E} L_e(\pi - \delta_e)/(4\pi)$$ Where $E$ is the set of all edges of the polyhedron, $L_e$ is the length of edge $e$ and $\delta_e$ is the interior ...
8
votes
1answer
374 views

Higher dimensional scutoids?

The recent discovery of scutoids in biological structures is fascinating. Two scutoids are depicted below (from Scientists Have Discovered an Entirely New Shape, And It Was Hiding in Your Cells), each ...
3
votes
0answers
54 views

How rich is the class of vertex- and edge-transitive polytopes?

There are only a few regular polytopes (five in 3D, six in 4D, three in any dimension above). In contrast, the class of uniform polytopes becomes very rich with higher dimensions. The class of vertex-...
3
votes
2answers
49 views

Complexity of 2D-Minkowski sum of non-convex polygons

I have read that the complexity of computing the Minkowski-Sum of $2$ non-convex polygons (through convex decomposition) is $O(m^2 n^2)$, where $m$ and $n$ is the number of vertices of each polygon. ...
4
votes
1answer
103 views

Continuity of the combinatorial structure of a polytope with respect to face variables

Suppose we are given a convex polytope in terms of the face variables. That is, let $Y = (1,x_1,\dots,x_n)$ and suppose we have vectors $W_a$ in $\mathbb{R}^{n+1}$ such that the locus $W_a \cdot Y \...
7
votes
0answers
210 views

Integral representations of finite groups and lattice point geometry

This contains both a reference request, and a specific problem. Let $K$ be a finite group, and let $\theta: K \to {\rm GL}(d,{\bf Z})$ be a (faithful) group representation over the integers. Consider ...
3
votes
0answers
83 views

Conjecture on tilting modules for an Auslander algebra

On page 13 of "Tilting modules for the Auslander algebra of $K(x)/x^n$" the author, Geuenich, suggests that the number ($p_{n,i}$) of isomorphism classes of modules, occurring as the $i$-th summand of ...
6
votes
1answer
127 views

Example of convex n-gon that cannot be decomposed into k congruent convex polygons

I asked a related question here on MO without any answers yet. The question is in the title - give an example of a convex $n$-gon that cannot be subdivided into $k>1$ congruent convex polygons. ...
0
votes
0answers
30 views

Realisation of a Polytope as a convex set [duplicate]

Suppose I have ALL the combinatorial data of an abstract Polytope: a list of all facets and incidence relations. Is there a way to produce linear functions, in a suitable $R^d$, so that the region ...
0
votes
0answers
138 views

Probability that the perturbed convex hull is larger than the original one

I am wondering if any convex geometers/probabilists have looked at the following question: Given $n$ randomly distributed (not sure what assumption to put there) points in $\mathbb{R}^d$, for each ...
0
votes
2answers
82 views

On OR condition in Linear Programming with exponentially many constraints [closed]

Suppose we have two linear programs $Ax\leq b$ and $Bx\leq c$ is there a way to combine them into one program of possibly a larger dimension $Cy\leq d$ such that projection of vectors $y$ into a ...
9
votes
3answers
346 views

Minimal combinatorial data needed to define a polytope [duplicate]

Suppose I give a list of vertices $(v_1, v_2, ..., v_n)$, and a list of "adjacencies", i.e. pairs of vertices $(v_i,v_j)$. Does it exists a unique polytope that has this vertices and realises the ...
1
vote
0answers
24 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 ...
4
votes
1answer
91 views

Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?

In OEIS A003436, it is written that the number of inequivalent labeled Hamilton Cycles of an n-dimesnional Octahedron is the same as the number of Perfect Matchings in a the complement of the Cycle ...
3
votes
0answers
114 views

Refined f- and h-partition polynomials of the associahedra

The f-polynomials, $F_n(x)$ (cf. OEIS A126216, A033282, and A086810), and the h-polynomials, $H_n(x)$ (cf. A001263, the Narayana polynomials), of the family of simple convex polytopes the associahedra ...
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 ...