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
0 votes
1 answer
76 views

Convex sets via fixed point equations

I have an equation of the general form $$ X = S \cup T X $$ where $S \subset \mathbb R^n$ is a convex polytope (given by its bounding hyperplanes), $T\colon \mathbb R^n \to \mathbb R^n$ is a linear ...
rimu's user avatar
  • 749
1 vote
0 answers
37 views

Polyhedra inscribed in a sphere with mutually non-congruent, equal area faces

Two constrained versions of the main question given in this post: Polyhedrons with mutually non-congruent faces, all of equal area. An earlier post that could be related: Cutting a spherical surface ...
Nandakumar R's user avatar
  • 5,401
1 vote
0 answers
92 views

Homeomorphism between interiors of simplex and permutohedron

The $n$-dimensional permutohedron $P_n$ is a polytope whose facets (i.e.\ codimension $1$ faces) are in 1-to-1 correspondence with all faces (of codimension${}\geq 1$) of the $n$-simplex $\Delta_n$, ...
Xin Nie's user avatar
  • 1,764
10 votes
1 answer
293 views

Is a convex polyhedron determined by its edge lengths and angular defects?

Let's consider 3-dimensional convex polyhedra $P\subset\Bbb R^3$. The angular defect at a vertex $v$ is $2\pi$ minus the sum of the interior angles of the incident faces at $v$. Question: Is a ...
M. Winter's user avatar
  • 12.5k
0 votes
0 answers
61 views

Using Ehrhart polynomials to count primes?

As indicated below, one could use the Ehrhart polynomials of the simplex in number theory. Here are the questions without context first: Questions: The sum $$\sum_{k=0}^t (-1)^k ( \operatorname{...
mathoverflowUser's user avatar
7 votes
3 answers
598 views

A continuous version of Carathéodory's convex hull theorem

A well-known theorem of Caratheodory states that any point in the convex hull of a set $X\subset R^n$ lies in the convex hull of at most $n+1$ points of $X$. I am wondering about a version of this ...
Mohammad Ghomi's user avatar
3 votes
0 answers
88 views

Sampling uniformly from the convex cone

Let $n$ vectors of dimension $d$ (e.g., $n = 100$, $d = 10000$), each with infinity norm of $1$, be given. The conic combination of those $n$ vectors generates a convex cone. How to uniformly sample ...
mathhamcs's user avatar
2 votes
0 answers
59 views

Eulerian polynomial from Bruhat interval - h* of something?

Let $\sigma \in S_n$ be a fixed permutation. Consider the polynomial $$ P_{\sigma}(t) = \sum_{\substack{\pi \in S_n \\ \pi \leq \sigma}} t^{\textrm{des}(\pi)} $$ where $\leq$ denotes Bruhat order, and ...
Per Alexandersson's user avatar
6 votes
0 answers
186 views

Zero-one pairings between sets of vectors

Let $A\subseteq V$ and $B\subseteq V^\star$ be spanning sets in a finite-dimensional real vector space $V$ and its dual $V^\star$. Suppose that $$ \langle b,a\rangle\in\lbrace0,1\rbrace $$ for all $a\...
Semen Podkorytov's user avatar
0 votes
1 answer
163 views

Density of the set of convex polygons in the Banach-Mazur distance

Is the set of convex polygons dense in the set of convex domains in $\mathbb{R}^2$, for the Banach-Mazur distance? Any insight for a negative or positive answer is very much welcome!
kvicente's user avatar
  • 171
3 votes
0 answers
92 views

Does there exist a finite-volume hyperbolic Coxeter polytope with these properties?

I searched for a finite-volume, hyperbolic Coxeter polytope of dimension $n \geq 4$ with the following properties $a$ and $b$. $a$) It has exactly one ideal vertex; $b$) if a bounded facet and an ...
Edoardo Rizzi's user avatar
3 votes
0 answers
49 views

Volume of all Voronoi cells in n-dimensional bounded space

How can one find the volume of all Voronoi cells (bounded and unbounded) in an $n$-dimensional bounded space? For instance, consider an $N$-dimensional space (hypercube) with bounds on each dimension ...
Maaz's user avatar
  • 131
0 votes
0 answers
54 views

existence of moment maps for non-nef toric varieties

The noncompact toric variety $X_1 = \operatorname{Tot} \mathcal{O}(-1) + \mathcal{O}(-1) \to \mathbb{CP}^1$, the total space of the sum of two line bundles over the complex line, is defined as the ...
jj_p's user avatar
  • 533
2 votes
0 answers
123 views

How to sample uniformly over a polytope knowing its vertex presentation?

Say that a convex polytope $P$ is presented as $P = \mathrm{Conv}(v_1, \dots , v_m)$. I would like to sample over $P$, without generating the facet presentation of the polytope. How can I do that? I ...
giulio bullsaver's user avatar
2 votes
1 answer
145 views

Conic hull of a rectangle

I have a simple question that appeared in research: For a rectangle $S :=[a_1,b_1] \times[a_2,b_2] \times \dots \times [a_n,b_n] \subset \mathbb{R}^n$. Let $p_0 = (a_1,a_2,\dots,a_n)$, and define $p_i ...
wsz_fantasy's user avatar
4 votes
1 answer
171 views

Denominators of rational polytopes in terms of hyperplane coefficients

Let $\mathcal{P}$ be a convex polytope in $\mathbb{R}^n$ given in the form $\mathcal{P} = \{ x \in \mathbb{R}^n\colon A x\leq b \}$. Suppose that the entries of $A$ and $b$ are integers. Then it is ...
Sam Hopkins's user avatar
  • 22.5k
3 votes
0 answers
120 views

Does this construct Platonic solids?

Consider $\mathrm{O}(3)\curvearrowright\mathbb{R}^3$. Let $\Gamma\subseteq\mathrm{O}(3)$ be a finite group. Let $x\in \mathbb{R}^3\setminus\{0\}$ be a point such that $\mathrm{Stab}_\Gamma(x)$ has ...
Display Name's user avatar
2 votes
0 answers
45 views

Estimating the Hausdorff distance of parallel facets of convex polytopes

Background Let $\mathcal{K}_P^n$ denote the class of open, convex, $n$-dimensional polytopes in $\mathbb{R}^n$ containing the origin. For each $K\in \mathcal{K}_P^n$, its gauge function $f_*:\mathbb{R}...
kenvergence's user avatar
4 votes
1 answer
279 views

Does Kalai's $3^d$ conjecture hold for simplicial spheres?

Kalai's $3^d$ conjecture asserts that every centrally symmetric $d$-polytope has at least $3^d$ non-empty faces. This is open in general, but has been proven for simplicial polytopes. Question: Does ...
M. Winter's user avatar
  • 12.5k
2 votes
1 answer
111 views

Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?

According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard. However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
Makogan's user avatar
  • 123
3 votes
1 answer
34 views

A converse question about the polyhedrality under linear mapping

It is quite well known that for any polyhedral set $K$ and any linear mapping $A$, the set $AK$ is polyhedral and hence closed. I am more curious about the converse problem, namely: Suppose $K$ is a ...
Wenqing Ouyang's user avatar
0 votes
0 answers
88 views

Which polytopes can be folded to an edge?

While playing with bar-and-joint linkages, I noticed that the skeleton of a regular 3-dimensional cube can be folded to a single edge (this can be achieved by first flexing the cube to bring it to a ...
Pritam Majumder's user avatar
3 votes
1 answer
99 views

Does a matroid base polytope contain its circumcenter?

Let $(X,\mathcal B)$ be a matroid on the ground set $X=(x_1,...,x_n)$ and with set of bases $\mathcal B$, and let $P\subset\Bbb R^n$ be its matroid base polytope (i.e. the convex hull of the ...
M. Winter's user avatar
  • 12.5k
6 votes
2 answers
237 views

"Minimal" connected matroids

I'm interested in connected matroids $M$ on the ground set $[n]$ for which there is no connected matroid on $[n]$ of the same rank but with a strictly smaller set of bases (by inclusion). Equivalently,...
Igor Makhlin's user avatar
  • 3,493
1 vote
0 answers
135 views

References/applications/context for certain polytopes

First, let's consider an almost trivial notion. With any subspace $V\subset \mathbb R^n$ we associate a convex polytope $P(V)\subset V^*$ as follows. Each of the $n$ coordinates in $\mathbb R^n$ is a ...
Igor Makhlin's user avatar
  • 3,493
0 votes
0 answers
37 views

Basis of monoid of integral vectors

Suppose that $M\in\mathbb{Z}^{n\times k}$ is a matrix of rank $k<n$. How can I obtain a set of vectors $b_1,\ldots,b_k\in\mathbb{Z}^k$ (if exists) such that each row of $M$ is a non-negative ...
Brauer Suzuki's user avatar
1 vote
0 answers
156 views

Membership test of convex set

Let $K$ be a compact convex subset of $R^n$ which has some positive gaussian measure, say at least 1/2. For each nonzero vector $u \in R^n$, we define another compact convex set $K * u$ in the ...
Sandra's user avatar
  • 11
4 votes
2 answers
210 views

On faces of polytopes

$\newcommand\ext{\operatorname{ext}}\newcommand\R{\mathbb R}$Let $A$ be a convex polytope in $\R^n$ with nonempty interior. Consider the closed convex cone $$K_A:=\{(l,t)\in(\R^n)'\times\R\colon\, l(x)...
Iosif Pinelis's user avatar
0 votes
1 answer
89 views

On the extreme points of two convex sets

Let $A$ and $B$ be two compact convex sets (which may be assumed to be polytopes) in $\mathbb R^n$ such that $A\cap B\ne\emptyset$. Is it then always true that either $A\cap\text{ext}B\ne\emptyset$ ...
Iosif Pinelis's user avatar
1 vote
0 answers
59 views

$\psi_2$ marginals of the permutahedron?

Let $K$ be a convex body. I in particular care about the permutahedron. I will view this as being the convex hull of all coordinate-wise permutations of the vector $$v = \frac{1}{2n+2}(-n, -n+2,\dots, ...
Mark Schultz-Wu's user avatar
1 vote
0 answers
71 views

Factorising a multivariate polynomial, in terms of products of linear polynomials, using blowups

I am considering multivariate polynomials of the form $$f(x,y)=x^a\,y^b\,p(x,y)^c$$ (and similarly for higher dimensions). I am trying to transform these polynomials into the generic form $$\widetilde{...
Giulio Crisanti's user avatar
8 votes
2 answers
336 views

Permutohedron and triangulation of cube via Eulerian numbers

The $h$-vector of the (simplicial complex given by the boundary of the polytope dual to the) permutohedron is the sequence of Eulerian numbers $A(n,k)=\#\{w\in S_n\colon \mathrm{des}(w)=k\}$. Example: ...
Sam Hopkins's user avatar
  • 22.5k
9 votes
1 answer
302 views

The convex hull of Schur polynomial evaluations

Let $r\leq n$ and $d$ be positive integers. A probability vector is a vector of non-negative entries that sum to 1. For each probability vector $\lambda$ of length $n$, let $$s(\lambda)=(\dim[\pi] \...
Ben's user avatar
  • 1,010
0 votes
0 answers
22 views

Reference on high dimensional polytopes with E8 symmetry

I'm starting to work with high dimensional polytopes. I am interested in uniform polytopes of 16-dimension and of 8-dimension (especially Elte and Gosset polytopes that have E8 symmetry). ...
Dac0's user avatar
  • 285
2 votes
0 answers
63 views

Sampling theorems for partition polynomials (associahedra, noncrossing partitions / parking functions)

Define the associahedra partition polynomial $$ \begin{split} A(x) &= 1 + A_1(u_1) z + A_2(u_1,u_2) z^2 + A_3(u_1,u_2,u_3) z^3 + \cdots\\ & \qquad\qquad = 1 + \sum_{n \geq 1} A_n(u_1,...,u_n) ...
Tom Copeland's user avatar
  • 9,897
4 votes
0 answers
216 views

How can we prove this combinatorial identity?

This is a follow up on my earlier MO post. Let's recall the sets $$\mathbf{K}_n=\{\mathbf{k}\in\mathbb{Z}^n: k_i\geq0, k_1+\cdots+ k_n=n, k_1+\cdots k_i\leq i, \text{for all $1\leq i\leq n$}\}$$ and $\...
T. Amdeberhan's user avatar
5 votes
1 answer
389 views

Catalan sequences vs composition sequences

In the paper, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Pitman and Stanley studied the $n$-dimensional polytope $$\Pi_n(\mathbf x)=\{y\in\...
T. Amdeberhan's user avatar
0 votes
0 answers
23 views

Approximation of connected set by triangluation / covering by simplices

Good afternoon. I have two distinct questions: If I have connected compact in $\mathbb{R}^n$, how much $(n+1)$-simplices are needed to fill its interior such that diameter of maximal uncovered part ...
Dmitry Vilensky's user avatar
4 votes
0 answers
46 views

Quantifying error in the reconstruction of convex polytopes from moments

The problem of reconstructing a geometric object from its moments is of interest in a variety of fields. In the paper The Inverse Moment Problem for Convex Polytopes, the authors show that a convex ...
Lucas Blakeslee's user avatar
4 votes
1 answer
136 views

Approximation of convex bodies by polytopes corresponding to smooth toric varieties

Let $P\subset \mathbb{R}^n$ be an $n$-dimensional polytope with rational vertices. There is a well known construction which produces an $n$-dimensional algebraic variety $X_P$ called toric variety. In ...
asv's user avatar
  • 21.1k
8 votes
1 answer
435 views

Do this polyhedron and other set have names?

Updated: My first post had a mistake because I confused in my mind two different but related sets. Hopefully the description below is correct now. Let $\Lambda$ be a finite set. Let $\Lambda^{(2)}$ be ...
Abdelmalek Abdesselam's user avatar
1 vote
0 answers
48 views

Fitting a convex polytope with 𝑛 facets between two nested spheres

This is related to a research problem that is interested in approximation of spheres by convex polytopes. Let $C_r$ and $C_R$ be two spheres in $\mathbb R^d$ of radius $r$ and $R$, respectively, where ...
pyridoxal_trigeminus's user avatar
1 vote
0 answers
39 views

About the number of faces of the conification of a polytope

Let $P\subset\mathbb{R}^n$ be a polytope of dimension $(n-1)$ such that the origin $\vec{0}\not\in\text{Aff}(P)$, where $\text{Aff}(P)$ denotes the affine hull of $P$ in $\mathbb{R}^n$. Now, we ...
ElliptCg's user avatar
  • 131
2 votes
1 answer
65 views

Example of worst case distributions for 4D convex hull

My understanding is that convex hull of n points in 4D could have O(n²) edges in the worst case. Source: https://sites.cs.ucsb.edu/~suri/cs235/ConvexHull.pdf This same source writes In 4D, there are ...
Alec Jacobson's user avatar
0 votes
1 answer
114 views

How can I find the hyperplane passing through a 600-cell

I have a 600-cell, whose coordinates are given by $$\begin{array}{ccc} \text{8 vertices} & \left(0,0,0,\pm1\right) & \text{all permutations,}\\ \text{16 vertices} & \frac{1}{2}\left(\pm1,\...
Dac0's user avatar
  • 285
1 vote
0 answers
26 views

Does Hoffman constant keep the same after a very tiny perturbation on the polyhedron such that the bases are even unchanegd?

Suppose that $P$ is a polyhedron represented by $$P:=\{x \in \mathbb{R}^n: A x \le b \} \text{ for }A \in \mathbb{R}^{m\times n},\ b \in \mathbb{R}^m,$$ and $P$ contains interior points. Moreover, the ...
ZZZZZZ's user avatar
  • 11
1 vote
0 answers
59 views

Polytope of a projected toric variety

I was looking for such a result in the book by Cox, Little and Schenck but I'm not able to find a proper reference. All of the following requirements are tacitly assumed to be in the projective ...
gigi's user avatar
  • 1,333
3 votes
0 answers
55 views

maximizing number of lattice points with bounded diameter

Suppose I have a lattice $L$ that's just $\mathbb{Z}^k$ but scaled in every coordinate by some (potentially different) real numbers. Now I want to construct a finite set of lattice points $S \subset L$...
Yan X Zhang's user avatar
0 votes
1 answer
88 views

Maximum number of vectors with bounds on inner products (follow up question)

This is a follow-up question from my previous question. Suppose there are (2n+1) vectors $\{m_1,m_2,...,m_n\}$, $\{p_1,p_2,...,p_n\}$ and $p^*$ in $R^{k+1}$. $m_i$ are weakly positive vectors. $p_i$ ...
TanG's user avatar
  • 23
4 votes
2 answers
238 views

Does the edge-graph of a centrally symmetric polytope determine which vertices are antipodal?

Given two origin symmetric convex polytopes $P_1$ and $P_2$ (that is $P_i=-P_i$) with the same edge-graph, but potentially of different dimensions and combinatorial types. Let $\phi: G_{P_1}\to G_{P_2}...
M. Winter's user avatar
  • 12.5k

1
2 3 4 5
19