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
1 vote
0 answers
19 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 ...
user avatar
12 votes
1 answer
367 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-...
user avatar
2 votes
1 answer
89 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 ...
user avatar
1 vote
0 answers
58 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 \...
user avatar
0 votes
0 answers
46 views

A sufficient condition for the decomposition of a bounded random vector

Given a matrix $A \in \mathbb{R}_{+}^{n\times m}$, where $n<m$ and rank($A$)=n. Define a set (a zonotope) $\mathcal{C}(A)=\{(x_1,x_2,\ldots,x_n)|\sum_{i=1}^m{\bf{a}}_ix_i,x_i \in [-1,1]\}$, where ${...
user avatar
5 votes
0 answers
50 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 ...
user avatar
0 votes
0 answers
41 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 ...
user avatar
  • 121
11 votes
0 answers
311 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 ...
user avatar
7 votes
0 answers
148 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 ...
user avatar
1 vote
0 answers
33 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 ...
user avatar
0 votes
0 answers
47 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\|:...
user avatar
0 votes
1 answer
94 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 ...
user avatar
  • 623
2 votes
1 answer
84 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 ...
user avatar
  • 195
6 votes
1 answer
135 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? ...
user avatar
  • 233
5 votes
0 answers
93 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 ...
user avatar
  • 1,318
0 votes
0 answers
49 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 ...
user avatar
5 votes
1 answer
124 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 ...
user avatar
  • 203
0 votes
0 answers
51 views

Projection onto a cone followed by a Schur-convex function

Let $Proj_C(x)$ denote the projection of a point $x$ onto a cone $C$. Let $f$ be a Schur-convex function. I'm considering $f(Proj_C(x))$ as a function of $x$. Are there any conditions on the cone $C$ ...
user avatar
  • 623
2 votes
0 answers
120 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 ...
user avatar
1 vote
1 answer
68 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 ...
user avatar
  • 5,600
2 votes
1 answer
102 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 ...
user avatar
  • 5,600
1 vote
1 answer
51 views

Optimal number of half-spaces in H-representation of convex-hall 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-...
user avatar
  • 5,600
6 votes
1 answer
458 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 ...
user avatar
  • 7,920
1 vote
1 answer
64 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\}, $$ ...
user avatar
  • 532
10 votes
3 answers
396 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\}$....
user avatar
  • 9,481
1 vote
0 answers
37 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 ...
user avatar
  • 185
4 votes
1 answer
91 views

How to solve this minimax matrix optimazation 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{...
user avatar
  • 532
2 votes
0 answers
50 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 ...
user avatar
  • 783
1 vote
0 answers
325 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'...
user avatar
  • 7,920
4 votes
1 answer
52 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 ...
user avatar
  • 375
3 votes
0 answers
94 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 ...
user avatar
  • 19k
3 votes
1 answer
172 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 ...
user avatar
  • 1,716
0 votes
0 answers
72 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?
user avatar
0 votes
1 answer
74 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}, ...
user avatar
0 votes
1 answer
91 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 ...
user avatar
2 votes
1 answer
122 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 ...
user avatar
  • 18.8k
3 votes
1 answer
76 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 $\{ (h h^T, h), h\in R^{d\times1}\}$. It is known that $\mathrm{cone}\{h h^T, h\in R^{d\times1}\}=S_+^d$, and $\mathrm{cone}\{h, h\in R^{d\times1}\...
user avatar
  • 108
24 votes
1 answer
529 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 ...
user avatar
1 vote
0 answers
68 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 ...
user avatar
  • 623
1 vote
1 answer
90 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?
user avatar
3 votes
1 answer
317 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 ...
user avatar
  • 2,949
0 votes
0 answers
72 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 ...
user avatar
1 vote
0 answers
46 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$ ...
user avatar
  • 375
4 votes
2 answers
350 views

Selecting vertices in a convex polygon

Given $n$ vertices of a convex polygon in $\mathbb{R}^2$, selecting two points that are furthest apart is done by finding the diameter in a convex polygon. But how can one select three vertices such ...
user avatar
8 votes
1 answer
133 views

The polytope algebras generated by polytopes with rational vs arbitrary vertices

The polytope algebra was defined by P. McMullen in "The polytope algebra" Adv. Math. 78 (1989) as follows. Let us denote by $\Pi'_\mathbb{R}$ the quotient of the free abelian group generated ...
user avatar
  • 19k
3 votes
0 answers
41 views

testing whether a polyhedral complex is convex

Definitions A (polyhedral) cone in $\Bbb R^n$ is the solution set of a finite number of inequalities of the form $a_1x_1+\cdots+a_nx_n\geq 0$. Note that I don't require strict convexity, i.e. a cone $...
user avatar
  • 2,921
1 vote
0 answers
65 views

Diminishing of the $4_{21}$

One of the projections of the $4_{21}$ polytope (https://en.m.wikipedia.org/wiki/4_21_polytope) into four dimensions positions its vertices as those of two concentric 600-cells scaled by the golden ...
user avatar
1 vote
1 answer
115 views

The relationship between facets of an inscribed polytope and those facets' shadows

I posted this question thinking that the response would be two or three answers that say "Counterexamples to this are found in every textbook—for example this one and this one and this one." ...
user avatar
1 vote
1 answer
127 views

High-dimensional polytopes

I have two questions regarding polytopes in high dimensions, $\mathbb{R}^d$ where $d > 3$, that I could not find resources for on the web for. Suppose I have a polytope that is non-convex: How can ...
user avatar
  • 43
3 votes
1 answer
62 views

Covering radius of a lattice from relevant vectors

Let $L$ be an $n-$dimensional lattice. The Voronoi region of $L$ is given by $$ \mathcal{V}(L)=\big\{x\in\mathbb{R}^n~|~ \|x\|_2\leq \|x-v\|_2~\forall v\in L\setminus\{0\}\big\}. $$ Considering the ...
user avatar
  • 33

1
2 3 4 5
17