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
942 questions
1
vote
0
answers
39
views
Partition complexity measure of the boolean cube?
Given $n$ points $p_1,\dots,p_n$ in $\{0,1\}^d$ my goal is to find $m$ index sets $\mathcal I_1,\dots,\mathcal I_m$ on the condition that each index set is a subset of $\{1,\dots,n\}$ on the ...
- 13.9k
11
votes
1
answer
2k
views
Characterizing faces of 3-dimensional polyhedra. (Related to Victor Eberhard's Theorem [1890]:)
Originally asked by Ali Dino Jumani; EXTENSIVELY EDITED by David Speyer. The previous version was a bit confused, but Steven Sivek and Graham, in the comments, figured out what was going on.
G. C. ...
1
vote
0
answers
261
views
Prove that the following set of triples forms a convex polytope
Take $a,\,b,\,c,\,d \in \mathbb R_+$ such that $a+b+c+d=1$. Define:
\begin{equation}
x_1 = \min(a+b,\,c+d)\,,\qquad x_2 = \min(a+c,\,b+d)\,,\qquad x_3 = \min(a+d,\,b+c)\;.
\end{equation}
I would like ...
- 31
1
vote
0
answers
89
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 ...
- 617
5
votes
1
answer
316
views
Coefficients of Ehrhart polynomials, in the binomial-coefficient basis
Let $P$ be the convex hull of a finite set of points in $\mathbb Z^d$, and $p(n) = \#\{nP \cap \mathbb Z^d\}$ be its Ehrhart polynomial, which is also the Hilbert polynomial of the corresponding ...
- 27.8k
9
votes
4
answers
475
views
Uniform Sampling Subject to Linear Equalities and Non-Negativity Constraint
I'm trying to sample uniformly on the intersections of faces of several simplicies, with all coordinates being non-negative. That is, given constraints
$$A\vec{w}=\vec{b} \ \ and \ \ \vec{w} \geq \vec{...
- 191
4
votes
2
answers
1k
views
How to (efficiently) find intersection of two polyhedral cones?
I have two polyhedral cones represented by their rays. I am looking to find their intersection, which would also be a polyhedral cone, hopefully efficiently. Does anybody know a way to do that?
...
13
votes
3
answers
1k
views
Triangulations of polyhedra
A topologist came to me with this question, but everything I think should work doesn't.
How many triangulations are there of a polyhedron with n vertices?
By a "triangulation" of a polyhedron P we ...
- 1,975
3
votes
1
answer
226
views
Is there a Fourier Analytic way to approximate volume?
Suppose a convex compact room in $3$-dimensions is given and source and microphones recorders are provided in the room that can locate echo timings there are works in literature which can give you the ...
- 13.9k
3
votes
1
answer
371
views
Approximating John's ellipsoid from uniform sampling of a centrally symmetric convex polyhedron
A centrally symmetric convex polyhedron in $\Bbb R^n$ shifted from the origin with possibly $e^{\alpha n}$ number of vertices at some $\alpha>0$ has an unique ellipsoid of maximum volume called ...
- 13.9k
4
votes
1
answer
3k
views
intersection of convex and non-convex polyhedra
I am trying to find the best appropriate way to intersect polyhedra which may be non-convex.
The number of vertices that build the polyhedron is hence always small (up to 20 or so).
The ...
- 143
7
votes
1
answer
274
views
Partitioning a convex object without harming existing convex subsets
$C$ is a convex planar figure and $C_1,\dots,C_n$ are pairwise-disjoint convex subsets of $C$, like this:
A convex-preserving partition of $C$ is a partition $C=E_1\cup\dots\cup E_N$, , such that $N\...
- 3,549
2
votes
0
answers
78
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)$ ...
- 373
3
votes
1
answer
158
views
Cyclic polytopes whose boundary is a flag complex
A cyclic polytope $C(n, d)$ is defined as the convex hull of $n$ distinct points on the moment curve in $\mathbb{R}^d$ (here $n>d$). This is a simplicial polytope so its boundary $\partial C(n, d)$ ...
- 1,017
1
vote
0
answers
68
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 ...
- 13
18
votes
1
answer
678
views
Higher dimensional generalization of: Any quadrilateral tiles the plane?
Any (non-self-intersecting) quadrilateral tiles the plane.
(MathWorld image.)
Q. What is the strongest known generalization of this statement to higher dimensions?
I.e., $\mathbb{R}^d$ ...
- 151k
4
votes
0
answers
221
views
Extending a Theorem of Brualdi to Matrices with Infinitely Many Rows
This question is about extending a result on transportation polytopes from Brualdi regarding $m\times n$ matrices to the case when $m=\infty$.
Notation: Denote an $m\times n$ matrix by $A=[a_{i,j}]$, ...
- 329
10
votes
1
answer
538
views
What's the volume of $\{x\in[0,1]^n|\sum x_i\le t\}$ for real $t$?
EDIT: Thanks for your answers and comments. There is indeed a classical easy formula, given by Pietro Majer (with a simple nice proof) in his answer below.
Given $x\in\mathbb{R}^n$, $x_i$ denotes its ...
- 1,855
1
vote
0
answers
48
views
Efficient scissors congruence between efficiently describable convex polytopes and simplex?
Is there a convex polytope in $\mathbb R^n$ describable by only $O(poly(\log n))$ half-plane inequalities with positive volume (so at least $n+1$ vertices) such that the standard simplex has a ...
- 1,826
8
votes
0
answers
194
views
intriguing Polytope
Define $E_{i,j} \in \mathbb{R}^{n \times n}$ to be the canonical basis (that is all elements set to zero except the entry $i,j$ )
let the bloc matrix $M \in \mathbb{R}^{n^2 \times n^2}$ defined by :
...
- 81
2
votes
0
answers
41
views
Describing hull of vertex intersections of two convex bounded polytopes?
We have two convex bounded polytopes $P_1$ and $P_2$ where
a. $P_2\subseteq P_1$
b. $\mathcal{V}(P_2)\cap\mathcal{V}(P_1)\neq\emptyset$.
Is there a name for the polytope $P=\mbox{Conv}(\mathcal{V}(...
- 13.9k
4
votes
0
answers
143
views
Reciprocity for multi-parameter Ehrhart polynomials
In McMullen's 1977 paper "Valuations and Euler-type relations on certain classes of convex polytopes" (https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s3-35.1.113), he shows that for $...
- 24.2k
1
vote
0
answers
92
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 ...
- 197
0
votes
0
answers
27
views
How do you refer to the feasible set of solutions to a mixed-integer program?
I frequently want to refer to the feasible set of solutions to a mixed integer programming instance. Is there a name for a subset of $\mathbb{R}^n\times\{0,1\}^m$ of the form $\{(x,a)| Ax + Ba\leq b\}$...
- 85
3
votes
2
answers
1k
views
The space of probability measures and its intersection with hyperplanes in the space of measures
Let $X$ be some uncountable standard Borel space (e.g., the real line).
Let $D$ be the set of Borel probability measures on $X$.
Let $M$ be the set of signed Borel measures on $X$
Now let $p_1,...,p_N$...
user12713
12
votes
2
answers
665
views
Detecting tilings by toric geometry
This is probably a silly question, but I figured that if there is a good answer, this would be a good place to ask.
Ever since I got my hands on the book "Toric Varieties" by Cox, Little and Schenck, ...
- 85.6k
-1
votes
2
answers
640
views
Maximal-Orthogonal Convex Hull (or Maximal-Rectilinear Convex Hull) [closed]
Edit : Consider giving a reason for down vote.
In my research, I have come across a this paper from the Computational Geometry field and I am not able to understand the concept of Maximal-...
- 119
1
vote
1
answer
2k
views
Computation of extreme rays of rational polyhedral cones - Hemmecke's project and lift algorithm
I am working on an implementation of Raymond Hemmecke's algorithm for finding generating sets of cones: http://arxiv.org/abs/math/0203105
Unfortunately I am struggling to make the algorithm work on ...
- 11
5
votes
1
answer
333
views
Delzant polytopes and combinatorial types
At first, let us see the following matheoverflow question,
About a Delzant polytope. (In particular dodecahedron)
The question is whether (combinatorial) regular dodecahedron can be realized as a ...
- 481
7
votes
3
answers
866
views
Not quite regular polyhedra
Take a naive interpretation of regular polyhedra:
All vertices (including epsilon ball) congruent
All edges congruent
All faces congruent
We can now find interesting families by removing one ...
- 1,314
4
votes
1
answer
316
views
A construction related to scissors congruence
I was thinking about the following some time ago. My question is whether such things have been studied before.
Let $E_n$ be the abelian group with a generator for each (bounded) euclidean polytope of ...
- 55.9k
3
votes
1
answer
452
views
How to find extreme points of a set related to Minkowski's Theorem?
Let $S^{n-1}$ be the unit sphere in $\mathbb{R}^n$. For $m>n$, we can define $\Lambda$ to be the set
$$\{(\lambda_1, ..., \lambda_m):\sum_{i=1}^m \lambda_i=1, \lambda_i\ge0, and \mbox{ there exist}...
- 1,350
1
vote
0
answers
121
views
Radial similarity of Newton polytopes
Let $k$ be a field of characteristic zero, and assume that $p,q \in k[x,y]$ is a Jacobian pair, namely, $p_xq_y-p_yq_x \in k^*$
(= the determinant of the Jacobi matrix $\in k^*$).
It is known that ...
- 2,837
1
vote
1
answer
290
views
Tutte polynomials and h-vectors of convex polytopes
Revised question:
Aluffi and Marcolli give a recursion relation for the Tutte polynomials of altered graphs (as described in Machacek's post below) on page 42 of "Feynman graphs and deletion-...
- 10.5k
2
votes
1
answer
404
views
Relating face polytopes of permutohedra to integer partitions
The OEIS entries A019538, A049019, and A133314, relate a refinement of the face polynomials of the permutohedra (A049019) to partition polynomials (A133314) defined by multiplicative inversion of an ...
- 10.5k
7
votes
1
answer
202
views
What polytope is this? Bounded sums with choice of coefficients
Let $b\gt a\gt 0$ be constants. Define $P_n(a,b)$ to be the set of all $(x_1,\ldots,x_n)\in\mathbb{R}^n$ satisfying
$$ |c_1 x_1 + \cdots + c_n x_n| \le 1$$
for every choice of $c_1,\ldots,c_n\in\...
- 37.7k
1
vote
0
answers
710
views
What is the significance of the $-1$-simplex?
The number of $k$-simplex elements in an $n$-simplex is counted by the binomial coefficient $\binom{n+1}{k+1}$. For example, the $3$-simplex is the tetrahedron, which has the following elements: $4$ ...
12
votes
1
answer
375
views
Why do convex polytope options constrict with dimension, rather than expand?
There are an infinite number of regular polygons in the plane,
five regular polyhedra,
six regular polytopes in $\mathbb{R}^4$,
and then three regular polytopes in every dimension $d > 4$.
There ...
- 151k
5
votes
2
answers
1k
views
regular polyhedra (and polytopes) in hyperbolic geometry, and generalisations
While there exist regular tesselations of the hyperbolic plane with arbitrary regular polygons, there are no new regular polyhedra in hyperbolic (3D) space. This being quite trivial, it is probably ...
- 3,630
14
votes
0
answers
205
views
Have there been further developments on this scheme for polytope approximations to the unit ball of $\ell_p^n$?
A long time ago I happened to look at, and save (on a floppy disk!) for future reading, a copy of the following article:
W. T. Gowers, Polytope approximations of the unit ball of $l^n_p$.
In Convex ...
- 25.8k
18
votes
1
answer
644
views
Egalitarian measures
A question I got asked I while ago:
If $T$ is a triangle in $\mathbb R^2$, is there a function $f:T\to\mathbb R$ such that the integral of $f$ over each straight segment connecting two points in the ...
- 47.3k
4
votes
3
answers
227
views
Cluster Variables for non-convex n-gons
Most of the lectures and lecture notes on Cluster Algebras (at least from Combinatorial point of view) start with mutations of the diagonals of a convex n-gon (mostly the pentagon) as the illustration ...
- 493
0
votes
2
answers
318
views
Lattice question
Consider a lattice $\mathcal{L} = \mathbb{Z}v_1 \oplus \ldots \oplus \mathbb{Z}v_l$ in $\mathbb{R}^n$ and let $S_0$ be the set of edges of the fundamental unit of $\mathcal{L}$. We call a region $X$ ...
- 501
9
votes
2
answers
1k
views
Regular polygon shadows of convex polyhedra
Fix a finite subset $S$ of the natural numbers $\mathbb{N}$, each element $\ge 3$.
Is there a convex polyhedron $P$ that has among its shadows
regular $n$-gons for each $n \in S$? Does such a $P$...
- 151k
8
votes
1
answer
725
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 ...
- 902
5
votes
2
answers
345
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 ...
- 22.8k
13
votes
3
answers
1k
views
When are Ehrhart functions of compact convex sets polynomials?
Given a lattice $L$ and a subset $P\subset \mathbb R^d$, we define for each positive integer $t$ $$f_P(L,t)=|(tP\cap L)|$$ the number of lattice points in $tP$. Let's say $P$ is nice if $f_P(L,t)$ is ...
- 85.6k
2
votes
1
answer
144
views
Intersection of segments in $\mathbf{R}^{k}$
Let $A$ be a set composed by an even number $n$ of distinct points in $\mathbf{R}^{k}$, such that any 3 points in $A$ are non-collinear in $\mathbf{R}^{k}$.
Let us consider the set $P_{2}(A)$ of ...
1
vote
1
answer
413
views
estimating binomial coefficients
There is a beautiful paper on the arXiv by Andrew Suk containing an asymptotic result about the Erdös-Szekeres convex polygon problem. I am struggling with one of the estimates he makes on page 4. He ...
- 7,637
1
vote
0
answers
74
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-...
- 11