Skip to main content

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
24 votes
1 answer
770 views

Given a group action on a simplex, can I always find a fundamental region that is a simplex?

Let $\Delta\subset\Bbb R^n$ be a simplex with $n+1$ vertices. Let $G\subset\mathrm{GL}(\Bbb R^n)$ be a finite group of linear symmetries of $\Delta$, i.e. linear transformations that fix the simplex ...
M. Winter's user avatar
  • 13.6k
1 vote
2 answers
538 views

Algorithm to find a facet of a polyhedron given the vertices?

I have a set of points $X=\{x_1,\ldots,x_N\}$ on the unit sphere in $\mathbb{R}^d$ ($N>d\ge 3$). What is an algorithm to find any facet of the polyhedron whose vertices are $X$? The set $X$ has ...
Ryan Bennink's user avatar
1 vote
1 answer
119 views

Volume ratio of polytopes with few vertices

The volume ratio of a convex body $K\subset \mathbb{R}^{n}$ is $v_r(K) = \inf_{\mathcal{E}\subset K} \left(\frac{Vol(K)}{Vol(\mathcal{E})}\right)^{1/n}$ where the infimum run over ellipsoids included ...
Gericault's user avatar
  • 245
3 votes
0 answers
151 views

Permutahedra Euler characteristic polynomials from cumulant-moment relation, a combinatorial proof?

Given the formal Taylor series, or e.g.f., $f(x) = 1 + \sum_{n \geq 1} m_n \; \frac{x^n}{n!}$, the classical formal cumulants $c_n$ are generated from the formal moments $m_n$ via $ \sum_{n \geq 1} ...
Tom Copeland's user avatar
  • 10.5k
4 votes
1 answer
117 views

Given a polytope $P$ with bipartite edge-graph, if the bipartition classes are equal in size and lie on spheres, is $P$ inscribed?

Suppose that $P\subset\Bbb R^n, n\ge 3$ is a (full-dimensional) convex polytope with a bipartite edge-graph $G=(V_1\cup V_2,E)$ (for example, a zonotope). Suppose further that there are concentric ...
M. Winter's user avatar
  • 13.6k
3 votes
0 answers
105 views

Simplex cover of an n-cube with non-congruent simplexes

I am curious about simplex coverings of the unit n-dimensional hypercube (or n-cube) with the following properties: The simplexes do not need to be regular The simplexes can be non-congruent (i.e. of ...
Sirplentifus's user avatar
1 vote
0 answers
154 views

Volume of a polytope as its degenerates to be lower dimensional

Consider a polytope $P$ defined by the usual inequalities $A\mathbf{x}\leq \mathbf{b}$; let me assume that $P$ is not contained in a proper subspace. A result which I believe to true, but am not ...
Ben Webster's user avatar
  • 44.7k
4 votes
1 answer
304 views

Do combinatorially equivalent polytopes have the same triangulations?

A triangulation of a convex polytope $P\subset\Bbb R^n$ is a partition of $P$ into $n$-simplices $\{\Delta_1,...,\Delta_m\}$ each of which has all its vertices among the vertices of $P$. A polytope ...
M. Winter's user avatar
  • 13.6k
1 vote
1 answer
87 views

Can upper bounds on totally monotone functions be taken (WLOG) to be themselves totally monotone?

Consider the following: fix a function $\bar{b} : \mathbf{R}_+ \to [0, \infty]$, and define \begin{align} \mathcal{S} \left( \bar{b} \right) := \left\{ b : \mathbf{R}_+ \to [0, \infty] \, \text{s.t.} \...
πr8's user avatar
  • 801
1 vote
0 answers
32 views

Adjacent vertices of a permutohedron which is the orbit of a point $x$ with repeated coordinates

Question: Let $x=(x_1, ..., x_n) \in \mathbb{R}^n$, and let $P$ be the convex hull of the points formed by permuting the coordinates of $x$. Given a vertex $y$ of $P$, what is a general rule for ...
ccriscitiello's user avatar
16 votes
2 answers
590 views

Can you perturb an inscribed polytope so all its edges grow?

Consider the family of convex simplicial polytopes with vertices in the unit sphere of $\mathbb{R}^n$ which have the origin as an interior point. My question is the following: Let $P, P'$ be two non-...
Miek Messerschmidt's user avatar
5 votes
2 answers
672 views

Secondary polytope

Given a polytope $P$, what do the points of the secondary polytope correspond to? I know that the vertices of the secondary polytope correspond to regular triangulations of $P$. But what do the ...
André Henriques's user avatar
2 votes
1 answer
137 views

What does the boundary of convex hulls look like in matrix Lie groups?

Let $G$ be a compact matrix Lie group under the Killing form metric $\langle \xi, \eta \rangle_g = -\frac{1}{2}\text{tr}((g^{-1}\xi)^T(g^{-1}\eta))$ for $g \in G$ and $\xi,\eta \in T_gG$. Let $C \...
Spencer Kraisler's user avatar
6 votes
0 answers
74 views

Roundest polyhedra: how well can we bound the edge count of their faces?

By "roundest" I mean having the lowest surface area for the highest volume, given a fixed number of faces $n$. There've been a few questions about them on here (including from me), but I'm ...
Robin Saunders's user avatar
0 votes
0 answers
146 views

Graduate level convexity - Intersection of an r-polytope with a hyperplane is an r-1 polytope

I am trying to follow Roger Webster's Convexity 's proof of Euler's celebrated result on the relationship between the number of faces of a polytope. An image of the proof is here. In the course of the ...
Tryer's user avatar
  • 121
11 votes
0 answers
345 views

Is my open set a ball?

Let $P$ be a polytope of dimension $n$, and let $\mathcal{C}$ be a polyhedral subdivision of $P$. That means that $\mathcal{C}$ is a finite collection of polytopes whose union is $P$, such that the ...
Nicholas Proudfoot's user avatar
7 votes
0 answers
227 views

Tiling space with supertile of hypercube unfoldings

Two students in my class asked and answered what might be a novel question. It is well known that the cube has exactly $11$ edge-unfoldings (or "nets"), as shown below:         (Image from ...
Joseph O'Rourke's user avatar
1 vote
0 answers
58 views

Are cells of 4-polytopes a convex polyhedron by definition?

I'm going by the Wikipedia definition for a 4-polytope. Do by definition, cells of 4-polytopes have to be a convex polyhedra? If not, then are there polyhedra with non-convex faces? If yes, is it the ...
Ron Michal's user avatar
0 votes
0 answers
74 views

Diameter of inner parallel body

Let's say I have a convex polytope $\mathcal{P} \subset \mathbb{R}^n$ with non-empty interior. Let $\mathcal{P}=\bigcap_{i=1}^mH_i$ for some halfspaces $H_i$ and let $d=diam(\mathcal{P})=\sup\{\|x-y\|:...
Jjj's user avatar
  • 93
0 votes
1 answer
101 views

Estimation via projecting onto a convex body

Assume that $\theta$ is in a convex body $K \in \mathbb{R}^n$ and we observe $y = \theta + z$, where $z$ is a noise term (following, say, the normal distribution). Consider an estimator of $\theta$ by ...
John Wong's user avatar
  • 773
2 votes
1 answer
145 views

Convex polytopes in other spaces

In all introductory texts I'm aware of, convex polytopes are dealt with strictly within $\mathbb R^n$. Being used to quite larger levels of generality elsewhere, I'm wondering if the same can be done ...
ViHdzP's user avatar
  • 447
8 votes
1 answer
361 views

Inscribed $n$-polytope with $2^n$ vertices of maximal volume

The question is in the title: Question: Which inscribed $n$-dimensional polytope (inscribed in the unit sphere) with $2^n$ vertices has the largest possible volume? Is it the $n$-dimensional cube? ...
M. Rumpy's user avatar
  • 283
5 votes
0 answers
167 views

Maximal number of vertices of the intersection of a flat and a hypercube

Consider the intersection of an $n$-dimensional hybercube and an $m$-dimensional flat (affine subspace) which contains the diagonal of the hypercube. This is a convex polytope. What is the maximal ...
Vanessa's user avatar
  • 1,368
0 votes
0 answers
118 views

Weak derivative of projection onto probabilist's simplex

Let $\Delta_n:=\{x\in [0,1]^n:\boldsymbol{1}^{\top}x=1\}$ denote the probabilist's $n$-simplex and let $P:\mathbb{R}^n\rightarrow\Delta_n$ denote the (Euclidean) metric projection onto this simplex ...
ABIM's user avatar
  • 5,405
6 votes
1 answer
277 views

Realizing spherical complexes as convex polytope

A spherical polytope is the intersection of some closed hemispheres which is non-empty and does not contain a pair of antipodal points. A spherical complex is a tiling of the whole (d−1)-dimensional ...
hyyyyy's user avatar
  • 305
2 votes
0 answers
221 views

Do the polyhedral homologies of a polyhedron coincide with the polyhedral homologies of its subdivision?

Definition. A convex polytope is a compact finite intersection of hyperplanes in $\mathbb{R}^n$ Definition. The polycomplex is the following data set: a set of convex polytopes, closed under ...
Arshak Aivazian's user avatar
1 vote
1 answer
139 views

On the Lipschitz continuity of the unit-normal vector field of a polytope

Let $\mu$ be a probability measure on $\mathbb R^n$ and let $P$ be a compact polytope in $\mathbb R^n$. For any $x \in \mathbb R^n \setminus P$, let $p(x) \in P$ be (unique!) point in $P$ which is ...
dohmatob's user avatar
  • 6,853
2 votes
1 answer
113 views

Existence of fine approximate of a convex body in $\mathbb R^d$ with convex hull of $\mathcal O(d)$ points

Let $K$ be a convex body in $\mathbb R^d$ which contains the origin and let $\theta \in (0,1)$. Question. Is it always possible to find $n$ points $x_1,\dotsc,x_n \in \mathbb R^d$ such that $$ \theta ...
dohmatob's user avatar
  • 6,853
2 votes
1 answer
137 views

Optimal number of half-spaces in the $H$-representation of the convex hull of $n$ points in $\mathbb R^d$

Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-...
dohmatob's user avatar
  • 6,853
9 votes
1 answer
889 views

Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory

In the background sections below, I establish the relations among characterizations of the action of Virasoro / Kac–Schwarz operators of 2D gravity models presented in terms of Laurent series by ...
Tom Copeland's user avatar
  • 10.5k
1 vote
1 answer
92 views

How to compute external angles of a hypersimplex?

Recently, I concern with the volume of the outer parallel body of a hypersimplex that is defined as follows $$ \mathcal{H}_s(n,k)=\left\{ (x_1,\cdots,x_n):\sum_{i=1}^n x_i=k,x_i\in[0,1] \right\}, $$ ...
RyanChan's user avatar
  • 550
10 votes
3 answers
500 views

Given the skeleton of an inscribed polytope. If I move the vertices so that no edge increases in length, can the circumradius still get larger?

Let $P\subset \Bbb R^n$ be an inscribed convex polytope, that is, all its vertices are on a common sphere of radius $r$. Let $G$ be the edge-graph of $P$. For convenience, assume $V(G)=\{1,\dotsc,s\}$....
M. Winter's user avatar
  • 13.6k
1 vote
0 answers
65 views

Minimum bounding rectangle of symmetric convex bodies in the plane : is the ball the worst case

The minimal rectangle containing the euclidean ball in the plane is the standard cube $B_\infty = [-1;1]^2$. I would like to know if the euclidean ball is the worst symmetric convex body to be ...
Gericault's user avatar
  • 245
4 votes
1 answer
194 views

How to solve this minimax matrix optimization problem?

Recently, I want to know how well can a $\ell_1$ ball be approximated by the image of a $\ell_2$ ball under a linear transform. I formulate this problem as the following optimization problem. \begin{...
RyanChan's user avatar
  • 550
2 votes
0 answers
61 views

Does absolute retract imply convex structure?

In the theory of selection, it is known that any compact absolute retract (AR) carries a convexity structure defined by E. Michael. It is also known that a convex structure developed by Van de Vel ...
Shijie Gu's user avatar
  • 2,083
1 vote
0 answers
370 views

Combinatorial proof of a matrix equation

I'm looking for combinatorial proofs (using, e.g., trees) of the following particular matrix equation $(I)$ and also combinatoric operational analogs of its solution via matrix inversion and/or Cramer'...
Tom Copeland's user avatar
  • 10.5k
4 votes
1 answer
74 views

Simplicial polytope with regular cones

Let $P$ be a convex simplicial polytope in $\mathbb{R}^n$. Can we find a convex simplicial polytope $P_0$ in $\mathbb{R}^n$ combinatorially equivalent to $P$, satisfying the following condition: The ...
user73577's user avatar
  • 405
3 votes
0 answers
179 views

Polytope algebra and toric vareties

Let $\Pi$ denote the McMullen polytope algebra (over the field of rationals $\mathbb{Q}$) generated by convex polytopes with rational vertices in $\mathbb{R}^n$. For a simple polytope $P$ let us ...
asv's user avatar
  • 21.8k
3 votes
1 answer
274 views

Unimodality of $f$-vectors of $0/1$-polytopes

It is known that the face vectors (aka $f$-vectors) of general polytopes need not be unimodal. This even fails for simple or simplicial polytopes, as was shown first by Björner. My question is if ...
Luis Ferroni's user avatar
  • 1,889
0 votes
0 answers
97 views

Possible new convex uniform polytope

Does there exist a convex uniform 9-polytope obtained by diminishing the 9-hypercube, removing 480 of its 512 vertices and turning each 8-hypercube facet into an 8-orthoplex?
Daniel Sebald's user avatar
0 votes
1 answer
175 views

Maximum vertex amount of low-dimensional simplex projection

Consider an arbitrary simplex $\mathcal{S} \subseteq \mathbb{R}^n$ ($\mathcal{S}$ is a polytope in $\mathbb{R}^n$ with $n+1$ vertices and non-empty interior). Let ${\bf P} \in \mathbb{R}^{m \times n}, ...
Daniel Turizo's user avatar
0 votes
1 answer
428 views

The dimension of the normal cone of a face in a polytope

Let $P$ is a polytope in $\mathbb{R}^n$ if $F$ is one of its faces of dimension $d$ then the dimension of its normal cone $\mathcal{N}(F)$ is $n-d$.\ This seems to be intuitively obvious but I can't ...
Mathlover's user avatar
2 votes
1 answer
133 views

Discrete random walk on polytope via involutions

Let $P$ be a convex polytope (or more generally convex body, I suppose) in $V=\mathbb{R}^n$. For each $v\in \mathbb{P}V$, we define an involution $\tau_v\colon P\to P$ by setting $\tau_v(p)$ to be the ...
Sam Hopkins's user avatar
  • 24.2k
4 votes
1 answer
195 views

What is the convex cone generated by the pair of rank 1 matrix and its eigenvector?

I'd like to know what is the convex cone generated by $\left\{ (h h^T, h) : h \in \Bbb R^{d\times1} \right\}$. It is known that $$\mathrm{cone} \left\{h h^T : h \in \Bbb R^{d \times1} \right\} = S_+^d$...
DASON's user avatar
  • 118
24 votes
1 answer
622 views

Polytope where each vertex belongs to all but two facets

Let $P$ be a (convex, bounded) polytope with the following property: for every vertex $v$, there are exactly two facets which do not contain $v$. Does it follow that $P$ is (combinatorially) a ...
Guillaume Aubrun's user avatar
1 vote
0 answers
83 views

Weird transportation polytope

I'm looking to compute extremal points of a weird polytope. This polytope contains all matrices with positive entries $A \in \mathcal M_{n,m}\left(\mathbb R_+\right)$ such that: every row sum except ...
lrnv's user avatar
  • 686
1 vote
1 answer
101 views

Graph diameter of the omnitruncated $E_8$ polytope

What is the graph diameter of the 1-skeleton of the omnitruncate of the $E_8$ family of uniform 8-polytopes?
Daniel Sebald's user avatar
3 votes
1 answer
351 views

Request for an article by Jim Lawrence

Jim Lawrence has a very important paper on the topic of valuations on polyhedra called "Rational-function-valued valuations on polyhedra", published in the DIMACS volume Discrete and ...
efs's user avatar
  • 3,107
0 votes
0 answers
165 views

Minimum circumscribed ellipsoid of $\mathcal H$-polytope

Given matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^n$, consider the $\mathcal H$-polytope $P$ defined as follows $$ P := \left\{ x \in \mathbb{R}^n : Ax \leq b \right\} $$ I ...
Daniel Turizo's user avatar
1 vote
0 answers
48 views

When is a PL function linear?

We have a simplicial decomposition of a $n$-dimensional disk $D_n$ an a PL function $\mu$ on the decomposition. For each set of vertices $v_1,\dots,v_n,v_{n+1}$, so that both $v_1,\dots,v_{n-1},v_n$ ...
user73577's user avatar
  • 405

1 2
3
4 5
19