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
3 votes
2 answers
329 views

Is a vertex- and edge-transitive polytope already a uniform polytope?

I want to consider (convex) polytopes $P=\mathrm{conv}\{p_1,...,p_n\}\subset\Bbb R^d$ which are both, vertex- and edge-transitive (or maybe stronger: 1-flag-transitive). Question: Is every such ...
3 votes
3 answers
784 views

Find a convex hull that contains given points?

Suppose that you have vectors $a_{1},...,a_{m}$ in $\mathbb{R}^n$. Can you take $n$ among them, let $v_{1},...,v_{n}$ such that $a_{1},...,a_{m}$ belong to the convex hull of $(cn)v_{1},-(cn)v_{1},...,...
5 votes
2 answers
339 views

Finding the Boundary Faces of the Zonohedron

A zonotope is a linear combination of m vectors with coefficients in [0,1]: $Z = \{ \sum \lambda_i v_i : 0 \leq \lambda _i \leq 1 \}$. The fancy way is to say it's the Minkowski sum of line segments ...
8 votes
2 answers
484 views

Integer decomposition of dilated integral polytopes

For $n > 0$, let $P$ be an integral polytope, that is, the convex hull in $\mathbb{R}^n$ of points in $\mathbb{Z}^n$. Suppose that $\dim(P) = n$. Question: Given $d > n + 2$ is it true that $$ ...
2 votes
0 answers
120 views

Are there half-transitive convex polytopes?

I only consider convex polytopes, i.e. convex hulls of finitely many points. The (edge-)graph of a polytope $P\subseteq\Bbb R^d$ is the graph consisting of the polytope's vertices, two are adjacent if ...
7 votes
1 answer
347 views

Sampling uniformly from the vertices of a polytope

I'm looking for a reference on how to sample uniformly (and preferably efficiently, elegantly, etc.) from the vertices of a polytope. I gather that enumerating vertices is hard. I also note the MO ...
4 votes
0 answers
141 views

Name for facet of a cone containing all but one edge

Let $C \subseteq \mathbb R^n$ be a polyhedral cone, so generated by its edges ($1$-dimensional faces) and $F \subseteq C$ a facet (codimension $1$ face) of it containing every edge except $e$. In ...
1 vote
0 answers
39 views

Counting Zeros Under Unitary Action

Assume we have two polynomials $f_1$ and $f_2$ with Newton polytopes $A_1 , A_2 \in \mathbb{Z}^2$. Also suppose that coefficients of $f_1$ and $f_2$ are generic. Then we pick a unitary matrix $Q$ and ...
8 votes
1 answer
675 views

Number of simplicial polytopes with a given f-vector

Plenty of very nice literature is available on the characterization of f-vectors of simplicial complexes of diverse sorts (results by Billera, Bjoerner, Kalai, Stanley, among others). I mention, as an ...
5 votes
0 answers
129 views

Laplace Beltrami eigenvalues on surface of polytopes

The recently posted arxiv paper Spectrum of the Laplacian on Regular Polyhedra by Evan Greif, Daniel Kaplan, Robert S. Strichartz, and Samuel C. Wiese, collects numerical evidence for conjectured ...
2 votes
0 answers
86 views

Existence of a "generic enough" lattice point interior to a lattice triangle

Let $T$ be a lattice triangle in $\Bbb R^2$ (i.e. the convex hull of three noncolinear points in $\Bbb Z^2$), and assume it has at least one interior lattice point. Is it always possible to find a ...
1 vote
0 answers
67 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 ...
0 votes
1 answer
111 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 ...
0 votes
0 answers
165 views

Centrally symmetric neighborly polytopes

Let $P$ be a centrally symmetric $k$-neighborly $d$-polytope. Let $ P^* $ is polar (also dual) of $P$. Consider a polytope $Q^*$ , $Q^* \subset P^* $(not necessarily a face of $P^*$). By duality, $P\...
11 votes
3 answers
799 views

"Database" of simplicial polytopes/spheres

Reading through various papers on polytopes I have come across really interesting examples of simplical polytopes and non-shellable (or non-PL) simplicial spheres but sometimes it is hard to keep ...
1 vote
0 answers
85 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 ...
5 votes
1 answer
302 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 ...
5 votes
0 answers
293 views

Biggest (or large) rectangle in a polytope

I need an efficient method to construct a (hyper)rectangle inside a polytope with a lot of dimensions (say $100 < d < 1000$). Ideally I'd want the biggest possible rectangle, but as I don't ...
2 votes
0 answers
74 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
0 answers
42 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
0 answers
100 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 ...
3 votes
1 answer
528 views

Calculate the discrete set of points B which are in the convex hull of the set of points A

This problem is likely best described with the following picture: Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
1 vote
1 answer
106 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 ...
3 votes
1 answer
245 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 ...
6 votes
1 answer
939 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$. ...
10 votes
2 answers
202 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 ...
2 votes
1 answer
344 views

Several convex polytopes in a simplex; fix an extreme point for each; how many can be supported by a function monotonic on all line segments?

Sorry the title may be unclear. I do not know how to give it a good title..... Let $\Delta$ be a probability simplex of $R^N$; i.e. set of all points $x$ such that $x\geq0$ and $\sum_{k=1}^Nx^k\leq1$....
1 vote
0 answers
41 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\...
6 votes
0 answers
92 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 ...
4 votes
1 answer
378 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\...
3 votes
0 answers
75 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 ...
2 votes
1 answer
132 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)=\...
16 votes
3 answers
701 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 $...
2 votes
0 answers
110 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 ...
4 votes
2 answers
671 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{...
8 votes
2 answers
1k 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 ...
2 votes
0 answers
182 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 ...
1 vote
0 answers
71 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-...
1 vote
0 answers
68 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 ...
2 votes
1 answer
361 views

Angle between Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample

Definitions Let $\mathcal{C}$ be a convex polytope in $\mathbb{R}^{D}$ with $K$-facets $F_{1},\ldots,F_{K}$. I denote the normal vector of the $k^\mathrm{th}$ facet as $\mathbf{w}\_k=(w_{k1},\ldots,...
1 vote
0 answers
90 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 ...
2 votes
0 answers
48 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 ...
4 votes
1 answer
439 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 $...
8 votes
1 answer
491 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 ...
25 votes
7 answers
9k views

Uniformly Sampling from Convex Polytopes

How to choose a point uniformly from a convex polytope $P \subset [0,1]^n$ defined by some inequalities, $Ax < b$? (Here $A$ is an $m \times n$ matrix, $x \in \mathbb{R}^n$, and $b \in \mathbb{R}^...
4 votes
2 answers
466 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
1 answer
136 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 \...
13 votes
1 answer
527 views

Minuscule weights of parabolic sub-root systems are not far from dominant

Let $\Phi$ be a crystallographic root system in an $n$-dimensional Euclidean vector space $(V,\langle\cdot,\cdot\rangle)$. For a root $\alpha\in \Phi$ we use $\alpha^\vee := \frac{2}{\langle \alpha,\...
2 votes
0 answers
40 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 ...
0 votes
0 answers
163 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 ...

1
7 8
9
10 11
19