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
0 votes
0 answers
72 views

Software for computing polytopes

As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
AlexiosF's user avatar
0 votes
0 answers
57 views

Probability of being inside a convex n-dimensional polytop

I am currently conducting some post-grad research about wireless transmissions with uncertain transmission delays. As part of the research, each individual transmission is modelled using a probability ...
Florian Bauer's user avatar
0 votes
0 answers
38 views

Polyhedra volume, faces and edges from vertices

Given a set of vertices in 3D corresponding to a convex polyhedron, what is the most efficient way to find its volume, faces, and edges? I've found some techniques using convex hulls. But I think I ...
user1420303's user avatar
10 votes
1 answer
136 views

Is the face lattice of the cube a polytope graph?

The face lattice of a convex polytope $P\subset\Bbb R^d$ is the partially ordered set whose elements are the faces of $P$ ordered by inclusion. We can turn it into a graph by considering its Hasse ...
M. Winter's user avatar
  • 12.7k
2 votes
1 answer
196 views

The realization space of non-convex polyhedra - What is known?

The space $\mathfrak R_{\mathrm c}(P)$ of convex realizations of a (3-dimensional, spherical) polyhedron $P$ is known to be well-behaved: it is a contractible manifold of dimension $\#\text{edges}+6$ (...
M. Winter's user avatar
  • 12.7k
1 vote
1 answer
94 views

Alexandrov's uniqueness theorem in Minkowski spacetime

Suppose $P$ is a convex polyhedron in $\mathbb{R}^{2,1}$. Each face of $P$ comes with induced metric tensor, if the face is space-like, then it is euclidean metric; every time-like face is isometric ...
Anton Petrunin's user avatar
0 votes
1 answer
117 views

Centroid of Minkowski sum

Let $A$ and $B$ be two compact convex subsets of $\mathbb{R}^n, n\geq 2$. Assume $x_A$ and $x_B$ are their respective centroid. If we form the Minkowski sum $C=A+B = \{x+y\mid x\in A, y\in B\}$, what ...
F J's user avatar
  • 161
4 votes
0 answers
39 views

Implementation of Friedman's algorithm of reconstructing simple polytopes

In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...
mashedcarrots's user avatar
0 votes
1 answer
97 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
  • 759
1 vote
0 answers
40 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,705
1 vote
0 answers
108 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
11 votes
0 answers
321 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.7k
0 votes
0 answers
66 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
638 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
95 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
60 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
198 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
168 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
  • 191
3 votes
0 answers
96 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
52 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
59 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
3 votes
0 answers
135 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
154 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
174 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
  • 23.1k
3 votes
0 answers
121 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
47 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
283 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.7k
2 votes
1 answer
152 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
37 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
90 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
104 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.7k
6 votes
2 answers
258 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,503
1 vote
0 answers
136 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,503
0 votes
0 answers
38 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
159 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
212 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
98 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
60 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
75 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
370 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
  • 23.1k
9 votes
1 answer
312 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
  • 970
2 votes
0 answers
66 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,965
4 votes
0 answers
227 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
390 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
4 votes
0 answers
51 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
143 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.3k
8 votes
1 answer
443 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
52 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
41 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
72 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

1
2 3 4 5
19