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
4
votes
1
answer
124
views
Convex caps with prescribed edges and curvature
Let $G$ be the edge graph of a convex subdivision of a convex polygon $P$ in the plane. I would like to construct a convex polyhedral cap $C$ (with zero boundary values) over $P$ whose edges project ...
- 7,194
6
votes
1
answer
395
views
Normal polytopes - counterexample?
An integral polytope $P$ is normal if all lattice points inside the integer dilation $kP$ can be expressed as $p_1+p_2+\dots+p_k$, where $p_i \in P$ are lattice points.
I am looking for an example $P$...
- 15.8k
1
vote
1
answer
234
views
When is the second largest Gaussian r.v. the largest in the stochastic sense?
Let $X_1, \ldots, X_n$ be jointly Gaussian, each of which is marginally distributed as a standard Gaussian $N(0,1)$. It is well known that $\max |X_i|$ achieves the maximum in the stochastic sense if $...
- 773
1
vote
0
answers
69
views
Can sufficiently symmetric polytopes be uniquely reconstructed from their 1-skeleton?
General convex polytopes can not be uniquely reconstructed from their 1-skeleton1, as explained here. Not even the dimension is known from the skeleton, as e.g. the complete graph $K_n,n\ge 5$ is the ...
- 13.6k
4
votes
1
answer
172
views
The number of simplicial and general $d$-polytopes with $d+3$ labelled vertices
Micha Perles used Gale diagrams to compute the number of simplicial $d$-polytopes with $d+3$ vertices and of general $d$-polytopes with $d+3$ vertices. The computation can be found in Chapter 6.3 of ...
- 24.7k
7
votes
1
answer
288
views
Poincare-Hopf theorem for polytopes?
Is there an analogue of Poincare-Hopf theorem for polytopes?
I want to apply it in the following situation.
I have a polytope in $R^n$ and a smooth explicitly given vector field in $R^n$.
I want to ...
- 71
1
vote
0
answers
218
views
volume of the region above a simplex in a spherical cap
Consider the $n$-dimensional unit ball $B$ centered at the origin and a hyperplane $H$ that intersects $B$. Suppose that there is a simplex $S$ inscribed in $B\cap H$, so that the vertices of $S$ lie ...
- 216
4
votes
2
answers
437
views
Unimodular triangulation and Ehrhart polynomials
Let $P$ be a convex lattice polytope. Then it has a polynomial Ehrhart function.
I am interested in what can be said about the Ehrhart polynomial when
$P$ has any of the properties
is integrally ...
- 15.8k
4
votes
3
answers
531
views
reference for the cubical structure of the associahedra
I cannot find where I learned that the $n$-dimensional associahedron is a union of $n$-cubes. The vertices of the $n$-dimensional associahedron are the finite binary trees having $n+2$ leaves and ...
- 1,625
4
votes
1
answer
1k
views
Sampling point uniformly at random satisfying equality constraints
First of all, I apologize in advance if the question has already been asked in some way on this site and/or if there is a widely known solution to this problem.
The description of my problem is ...
- 143
5
votes
0
answers
311
views
Biggest (or large) rectangle in a polytope
I need an efficient method to construct a (hyper)rectangle inside a polytope with a lot of dimensions (say $100 < d < 1000$). Ideally I'd want the biggest possible rectangle, but as I don't ...
2
votes
0
answers
385
views
(Quasi) convexity of separately convex homogeneous functions
Consider a function $f:\mathbb{R}^n_{\geq 0}\rightarrow \mathbb{R}$ that is separately convex, i.e. such that $\frac{d^2f}{dx_i^2}\geq 0$ for all $i\in \{1,\dots n\}$. Assume also that $f$ is ...
- 389
5
votes
2
answers
184
views
Differentiability of polytope shadow areas
Let $P$ be an opaque convex polyhedron containing the origin in $\mathbb{R}^3$,
and let $S$ be an origin-centered sphere strictly containing $P$: $S \supset P$.
For a point $x$ on $S$, let $\sigma(x)$ ...
- 151k
7
votes
1
answer
648
views
Maximal volume of a simplex inscribed in a spherical cap
Let $B_n$ be the $n$-dimensional unit ball, and $B_n(\varepsilon)$ be the spherical cap with height $\varepsilon$ I am interested in the quantity
$$\Gamma:=\sup_{\Delta:\textrm{ inscribed simplex in }...
- 599
7
votes
1
answer
756
views
Generalized permutahedron and random polytopes
The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the ...
- 407
4
votes
1
answer
158
views
Lifting of a spherical graph
Let us be given a topological graph $G$
on the unit sphere in $\mathbb{R}^3$
whose edges are minor arcs of great circles.
We suppose that the graph is $3$-vertex-connected
and that a pair of edges may ...
- 1,724
8
votes
6
answers
1k
views
Combinatorial distance ≡ Euclidean distance
Definition: A polytope has property X iff there is a function f:N+ → R+ such that for each pair of vertices vi, vj the following holds:
disteuclidean(vi, vj) = f(distcombinatorial(vi, vj))
with ...
- 9,720
3
votes
2
answers
792
views
Has anyone developed a technique to generate a polytope given (possibly redundant) inequality constraints? [closed]
I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm just trying to find the vertices for a feasible region, given a set of inequality ...
- 131
6
votes
2
answers
408
views
Triangulations of special polyhedra
Let $A_1,A_2,A_3 \in \mathbb{N}^3$ be three points in space all lying in some plane $x+y+z=d$ where $d$ is a positive integer. If $\{e_1,e_2,e_3\}$ is the standard basis in $\mathbb{R}^3$, we can ...
- 213
4
votes
0
answers
88
views
Maximum number of integer points in a polytope
What is the maximum number of integer points $\#M$ in a dimension $n$ closed bounded convex polytope $M$ given by $Ax\leq b$ with number $m$ of constraints and $O(d)$ bits in any entry of $A\in\Bbb Z^{...
- 13.9k
0
votes
1
answer
362
views
For a convex function, can subgradients be formed from finite convex combinations of gradients?
Let $f:\mathbb{R}^n \rightarrow \mathbb{R}$ a convex function. Since convex functions are locally Lipschitz, they are differentiable almost everywhere. Let $\delta f(x)$ be the set of subgradients to $...
- 147
3
votes
1
answer
81
views
Polytopes that are just defined by ordering the variables
I am working with a polytope with a very specific structure, namely that it is characterized entirely by placing the variables, or the variables plus constants, or just constants, in a particular ...
- 4,049
1
vote
0
answers
386
views
About hyperplanes cutting the discrete hypercube
Given $\{-1,1\}^n$ we randomly choose a hyperplane in $\mathbb{R}^n$. Now given an integer $p \in [1,n]$ and a number $\epsilon \in [0,1]$, I want to ask, "How likely is it that at least one of the $p-...
- 2,246
3
votes
2
answers
595
views
Number of facets of a polyhedron when a vertex is removed
My question, informally: I have a bounded polyhedron in R^n with k facets, and I want to remove a vertex of this problem. How many facets does the remaining polyhedron have at most?
More formally: ...
4
votes
0
answers
181
views
Keep doing it: generalized Catalan
One more time, let us see how else the Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$ can be generalized. First recall the generating function
$$C(x):=\frac{1-\sqrt{1-4x}}x=\sum_{n\geq0}C_n\,x^n.$$
...
- 43.2k
3
votes
2
answers
244
views
How many different integer polytopes does square lattice have?
Let $E_n = \{ (i,j) : 0 \leq i,j \leq n-1 \}$. We say that a polytope $P$ is an integer polytope in $E_n$ if all vertices of $P$ belongs to $E_n$.
My question is how many different integer polytopes ...
- 655
2
votes
0
answers
29
views
When do projection maps of polyhedra factor?
Given three polyhedra $P$, $Q$, and $R$ in dimensions $a$, $b$, and $c$ respectively, with $a\leq b\leq c$, with the additional condition that: $P=\pi_1(Q)=\pi_2(R)$, where $\pi_1$ and $\pi_2$ are ...
- 1,826
1
vote
0
answers
39
views
Counting Zeros Under Unitary Action
Assume we have two polynomials $f_1$ and $f_2$ with Newton polytopes $A_1 , A_2 \in \mathbb{Z}^2$. Also suppose that coefficients of $f_1$ and $f_2$ are generic. Then we pick a unitary matrix $Q$ and ...
- 351
1
vote
0
answers
126
views
What is an umbilic point of a convex polyhedron?
An umbilic point of a smooth ($C^2$) convex surface in Euclidean 3-space is a point where the principal curvatures are equal. Is there some good way to generalize this notion to convex polyhedra? See ...
- 7,194
4
votes
2
answers
975
views
Vertices of a Polytope
Given two convex polytopes $P,Q$ such that $P\subset Q$. We are given that all the vertices of $P$ are also vertices of $Q$ and all the facets defining planes of $Q$ are also facets defining planes of ...
- 505
5
votes
1
answer
387
views
Extreme rays in the cone of (semi)metrics
How many extreme rays are there on the polytopal cone formed by all semimetrics on a set with $n$ elements?
Some background. Given a set $X$ with $n$ elements, the set of all semimetrics
$d:X \times ...
- 13.5k
7
votes
1
answer
1k
views
Approximation of convex body by polytopes
In a recent survey paper, Approximation of convex sets by polytopes, Bronstein claims that under Hausdorff distance $\rho_H$, for every convex body $U$,
$$\rho_H(U,\mathcal{P}_n)\leq c(U) n^{-2/(d-1)},...
- 599
5
votes
1
answer
320
views
Non-closed geodesics on a convex polyhedron in $\mathbb{R}^3$
Let $P$ be the surface of a closed convex polyhedron in $\mathbb{R}^3$.
Q. Does every non-closed geodesic $\gamma$ fill $P$ densely?
Of course $\gamma$ cannot pass through a vertex of $P$, but it ...
- 151k
6
votes
2
answers
386
views
Are shortest halving curves simple closed geodesics?
Let $S$ be a smooth convex surface in $\mathbb{R}^3$
(although my question may as well be asked for the surface of a polyhedron).
Say that $\gamma$ is a shortest halving curve if
(a) it partitions the ...
- 151k
1
vote
1
answer
155
views
Derive a vertex representation of a permutohedron from its linear-inequalities form
Let us define the $n$-permutohedron $P_n$ as the set of all $x\in\mathbb{Q}^n$ such that
$$\sum_{i=1}^n x_i = \binom{n{+}1}{2}\ \ \ \land\ \ \ \forall\,\text{nonempty}\ S\subsetneq\mathbb{N}_n\colon\ ...
user94257
3
votes
0
answers
84
views
condition on rational polyhedral cone to guarantee dual cone is homogeneous
Let $\sigma\subseteq \Bbb R^d$ be a full-dimensional rational polyhedral cone which is strongly convex (i.e. $\sigma\cap-\sigma=0$).
Definition. The cone $\sigma$ is homogeneous if there are ...
- 3,079
1
vote
1
answer
1k
views
Extreme points of convex hull of Minkowski sum [closed]
Let $\operatorname{conv}(a_1,\ldots,a_m)$ denote the convex hull of $\{a_1,\ldots,a_n\}$. Let $P = \operatorname{conv}(a_1,\ldots,a_p)$ and $Q = \operatorname{conv}(b_1,\ldots,b_q)$ be two convex sets ...
- 1,713
10
votes
2
answers
930
views
What is determined by the combinatorics of the shadows of a convex polyhedron?
Define the shadow of a convex polyhedron $P$ in direction $u$
to be the orthogonal projection of $P$ onto a plane whose normal is $u$.
The shadow is a convex $k$-gon.
I am wondering to what degree $P$ ...
- 151k
6
votes
0
answers
191
views
Cut locus on a hypercube
Inspired by the question, "Shortest path connecting two opposite points on a cube":
Q. What does the cut locus with respect to one corner of a hypercube
in $\mathbb{R}^d$ look like?
"The cut ...
- 151k
7
votes
1
answer
819
views
Has this generalization of a determinant (assigning multiplicities to the rows) been studied?
I'm working on some questions in tropical geometry, and my problem led me to create the following generalization of a determinant:
Let $A$ be an $m \times n$ matrix with $m \le n$, and positive ...
- 1,509
17
votes
1
answer
1k
views
Totally rational polytopes
Define a convex polytope in $\mathbb{R}^d$ as
totally rational (my terminology)
if its vertex coordinates are rational, its edge lengths
are rational, its two-dimensional face areas are rational, etc.,...
- 151k
0
votes
1
answer
212
views
How to find out if a polytope contains a sphere?
Given a polytope described by linear inequalities $Ax \le b, x \in \mathbb R^n$, how do you find out if there exist a (non degenerate) sphere of dimension $n-1$ contained in the polytope?
Thanks!
- 225
5
votes
3
answers
457
views
Cellular decomposition of a sphere to polytope
My primary question is: given a cellular decomposition of a sphere is there any way to check if it can be embedded as the boundary of a polytope?
My question is motivated by the following problem. I ...
- 360
2
votes
0
answers
51
views
2-dimensional smooth lattice polytopes with minimal edge lengths
For each integer $k \geq 3$, does there exist a full-dimensional, $2$-dimensional, smooth lattice polytope $P$ with $k$ edges, such that each edge contains only two lattice points (i.e. only its ...
- 197
4
votes
2
answers
438
views
How to show that convex polytope is not a Voronoi cell?
Given a combinatorial type of a convex polytope, what techniques are available for showing that it cannot be realized as a Voronoi cell of some point system?
- 907
0
votes
0
answers
42
views
When is the set of faces of a convex polytope algebraically independent?
This is related to another question of mine
Let $V=\Bbb R^n$. Morelli defined the (commutative unital) ring $L(V)$ to be the additive group generated by the indicator functions of convex polytopes in ...
- 3,079
5
votes
1
answer
268
views
what's the formula of the inradius of a general simplex? [closed]
As the title, I just want to know whether there is a general formula for calculating the inradius of a n-simplex. Thank you!
- 51
6
votes
1
answer
347
views
Measurement of "symmetry" of a convex body
I often hear that the regular simplex is "the least" symmetric convex body, and I've heard that there are some measures of symmetry of a body, that the simplex minimizes.
Could you please explain or ...
- 1,893
5
votes
1
answer
384
views
Examples of Polyhedra with Large Shadows
Let $P \subseteq \mathbb{R}^n$ be a polyhedron described by $\mathcal{O}(n^{c_1})$ inequalities, where $c_1$ is a constant. Moreover, let $M\colon P \to \mathbb{R}^2$ be a linear mapping. I'm looking ...
- 321
3
votes
0
answers
970
views
Testing if a point is inside a convex polytope formed by halfspaces in n-dimension
Assume we have a convex polytope that is formed by the intersection of $k$-halfspaces in $\mathbb{R}^{n}$.
$$
a_{0,0}x^{n-1} + {a}_{0,1}x^{n-2} + ... a_{0,n-1} \leq 0
$$
$$
a_{1,0}x^{n-1} + {a}_{1,...
- 31