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
126
views
Mixed integer formulation of union of polytopes?
Given $t$ different unbounded polyhedra $P_1:A^{(1)}x^{(1)}\leq b^{(1)},\dots,P_t:A^{(t)}x^{(t)}\leq b^{(t)}$ we are looking for the representation of $\bigcup_{i=1}^tP_i$ (not their convex hull) with ...
- 1,826
2
votes
0
answers
92
views
Integrality of integral polytope?
Given a convex polytope with integral vertices presented in half-space description is there a way to test in
polynomial time or
polynomial hierarchy
if polytope has integral volume?
Finding ...
- 13.9k
7
votes
1
answer
295
views
Section of an $n$-dimensional convex polytope by $2$-dimensional plane
Consider an $n$-dimensional convex polytope with $k$ vertices. In the worst case the number of faces is exponential in $n$ and $k$. Consider a $2$-dimensional plane which intersects this polytope, i....
- 415
3
votes
1
answer
554
views
Calculate the discrete set of points B which are in the convex hull of the set of points A
This problem is likely best described with the following picture:
Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
- 151
0
votes
0
answers
369
views
Finding a point in the relative interior of the convex hull of a set of integer-valued vectors
Let $X \subset \mathbb{Z}^n$ be the set of integer-valued vectors satisfying a system of linear constraints. We can suppose that $X$ is the set of integral points in a given polyhydral set $Y \subset \...
- 136
2
votes
0
answers
126
views
Are there half-transitive convex polytopes?
I only consider convex polytopes, i.e. convex hulls of finitely many points. The (edge-)graph of a polytope $P\subseteq\Bbb R^d$ is the graph consisting of the polytope's vertices, two are adjacent if ...
- 13.6k
2
votes
0
answers
184
views
Can projecting a simplex onto orthogonal subspaces exposes the same vertices and edges?
Given the regular $n$-dimensional simplex $S\subset\Bbb R^n$ with $n\ge 4$, as well as two orthogonal subspaces $V,W\subset\Bbb R^n$ of dimension $\ge2$ (not necessarily of same dimension, not ...
- 13.6k
5
votes
0
answers
132
views
Laplace Beltrami eigenvalues on surface of polytopes
The recently posted arxiv paper Spectrum of the Laplacian on Regular Polyhedra
by Evan Greif, Daniel Kaplan, Robert S. Strichartz, and Samuel C. Wiese, collects numerical evidence for conjectured ...
- 3,209
11
votes
3
answers
6k
views
Random Sampling a linearly constrained region in n-dimensions...
Hi,
So here is my problem:
Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$
$x_n \le c_n$
and $\sum_{n=1}^N x_n = 1$ find an ...
- 113
4
votes
1
answer
625
views
The geometric explanation of **isotropic position**
A convex body $K$ in $\mathbb{R}^n$ is in isotropic position if, for all vectors $x \in \mathbb{R}^n$, we have
$$\frac{1}{\mathrm{vol}(K)}\int_K \langle x, y \rangle^2 dy = \|x\|^2.$$
My question: ...
- 49
18
votes
1
answer
641
views
Can all convex polytopes be realized with vertices on surface of convex body?
The following question was asked by me on Mathematics.SE. Unfortunately, no one answered it so I thought I might give it a try one level higher. Below the line you can find the slightly edited ...
- 907
1
vote
0
answers
68
views
Projection of a polytope along 4 orthogonal axes
Consider the following problem:
Given an $\mathcal{H}$-polytope $P$ in $\mathbb{R}^d$ and $4$ orthogonal vectors $v_1, ..., v_4 \in \mathbb{R}^d$, compute the projection of $P$ to the subspace ...
- 11
13
votes
2
answers
2k
views
Combinatorics of the Stasheff polytopes
First a little background for those unaware. The Stasheff polytopes (or associahedra) are certain convex polytopes that arise in the theory of $A_\infty$-algebras. There is one polytope for each $n\...
- 3,423
0
votes
0
answers
62
views
Looking for a homogeneous function with some properties
I'm looking for a 1-homogeneous function $\pi \colon \mathbb{R}^n_{\geq 0} \to \mathbb{R}$ satisfying the following properties:
1) $\pi$ is not concave. This is equivalent to the fact that there ...
- 357
-1
votes
2
answers
114
views
On OR condition in Linear Programming with exponentially many constraints [closed]
Suppose we have two linear programs $Ax\leq b$ and $Bx\leq c$ is there a way to combine them into one program of possibly a larger dimension $Cy\leq d$ such that projection of vectors $y$ into a ...
- 13.9k
7
votes
2
answers
605
views
Gaussian and the convex hull of moment curves
Let $c_1,\dots, c_d$ be the first $d$ moments of the standard normal distribution. Does the point $(c_1,\dots, c_d)$ lie in the convex hull of the set $\{(t,t^2,\dots,t^d)\colon t\in[-b,b]\}$, for a ...
- 1,127
3
votes
3
answers
793
views
Find a convex hull that contains given points?
Suppose that you have vectors $a_{1},...,a_{m}$ in $\mathbb{R}^n$. Can you take $n$ among them, let $v_{1},...,v_{n}$ such that $a_{1},...,a_{m}$ belong to the convex hull of $(cn)v_{1},-(cn)v_{1},...,...
user31317
9
votes
1
answer
3k
views
Linear transformation of a polyhedron
Is there a simple proof that shows:
Linear transformation of a $\mathcal{H}$-polyhedron (i.e. the intersection of
finitely many closed half-spaces) is a $\mathcal{H}$-polyhedron.
Minkowski sum of ...
- 1,991
1
vote
0
answers
49
views
Realizing 0/1-polytopes with shortest possible edge lengths
Has there been something written about the following question?
Question: Given a 0/1-polytope, what is the shortest edge lengths with which this polytope can be realized as a 0/1-polytope.
The ...
- 13.6k
10
votes
2
answers
326
views
Do maximal polyhedra have algebraic volume?
Is it possible to prove that for every $n > 3$ the maximal possible volume of a convex polyhedron having $n$ vertices inscribed in a sphere of unit radius is an algebraic number?
Update: What can ...
- 6,819
2
votes
1
answer
159
views
Counting lattice points can some give all?
Given convex polytope $\mathcal P\subseteq\Bbb R^n$ with $\mathcal P_\Bbb Z\leq2^n$ integer points and given locations of $O(\log \mathcal P_\Bbb Z)$ integer points in some positions can we obtain $\...
- 13.9k
1
vote
0
answers
79
views
What is known about the combinatorics of the hyperplane arrangement spanned by cyclic polytopes?
Let $1\leq d$ be an integer.
Consider the $d$-dimensional moment curve $\mu\colon \mathbb R\to \mathbb R^d$ given by $t\mapsto (t,t^2,\dots, t^d)$. Given a finite subset $S\subset \mathbb R$ of ...
- 725
3
votes
0
answers
181
views
Refined f- and h-partition polynomials of the associahedra
The f-polynomials, $F_n(x)$ (cf. OEIS A126216, A033282, and A086810), and the h-polynomials, $H_n(x)$ (cf. A001263, the Narayana polynomials), of the family of simple convex polytopes the associahedra ...
- 10.5k
1
vote
0
answers
64
views
Polytopes that can be efficiently described and efficiently covered by cubes or simplices?
Is there a bounded convex polytope $\mathcal P\subseteq\mathbb R^n$ with $m$ vertices, whose vertex vectors span $\mathbb R^n$ (so $m$ is $\Omega(n)$) and just $O(poly(\log n))$ half-plane ...
- 1,826
1
vote
0
answers
43
views
Vertex enumeration for polytope with a sparse halfplane description?
Say I have a (bounded convex) polytope $P\subset\mathbb R^d$ with description $Ax\le b$, where $A$ is sparse in the sense that there are at most $k$ nonzero entries in each row or column, where $k$ is ...
- 523
7
votes
2
answers
789
views
"MultiCatalan numbers"
Could anyone provide a reference for the following (sort of) generalization of Catalan numbers: the multinomial coefficient
$$
\binom{2k_1+3k_2+4k_3+...}{k_1+2k_2+3k_3+...,k_1,k_2,k_3,...}
$$
is ...
- 18.4k
0
votes
0
answers
165
views
Probability that the perturbed convex hull is larger than the original one
I am wondering if any convex geometers/probabilists have looked at the following question:
Given $n$ randomly distributed (not sure what assumption to put there) points in $\mathbb{R}^d$, for each ...
- 133
8
votes
2
answers
573
views
Decomposition of a cross-polytope into simplices
Consider the standard embedded $n$-cross polytope $P_n$ with vertices $\pm e_i \in \mathbb R^n$. Let us consider decompositions of this polytope into $2^{n-1}$ simplices, such that these simplices ...
- 11.9k
0
votes
0
answers
196
views
Generalizations of 'Injectivity on one line'
The main result of J. Gwozdziewicz in this paper says the following:
"Let $k$ be an algebraically closed field of characteristic zero, and let $f:k[x,y] \to k[x,y]$, $(x,y) \mapsto (p,q)$, be a $k$-...
- 2,837
7
votes
2
answers
392
views
Convex deltahedra in higher dimensions
There are eight convex polyhedra whose faces are equilateral triangles, so-called
deltahedra:
(Image from here)
Q. Have the equivalent higher-dimensional ...
- 151k
2
votes
0
answers
87
views
Existence of a "generic enough" lattice point interior to a lattice triangle
Let $T$ be a lattice triangle in $\Bbb R^2$ (i.e. the convex hull of three noncolinear points in $\Bbb Z^2$), and assume it has at least one interior lattice point. Is it always possible to find a ...
- 3,079
0
votes
1
answer
39
views
Gluing simplices through a common point/ realisation of a convex simplicial polytope
Given $m≥d+1$
a positive integer, is it always possible to find m d-dimensional simplices $\Delta_i=\mathrm{Conv}(M,V_{i,1},…,V_{i,d})$ such that
1) they all share the common vertex M
2) the ...
- 1,435
4
votes
2
answers
812
views
Is it possible to sample uniformly on the surface of a high-dimensional polytope?
There are some pretty simple methods to do uniform sampling on the surface of high-dimensional spheres or cubes.
Are there any methods that sample uniformly on the surface of a high-dimensional ...
- 143
3
votes
0
answers
315
views
Factorization of tropical polynomials
I am referring to the definition of a tropical polynomial given on page 8 (top of section 3) here in this review, https://arxiv.org/pdf/math/0306366.pdf. I understand that here a tropical polynomial ...
- 2,246
4
votes
5
answers
728
views
Lattice points in dilated polytopes and sumsets
Let $P$ be an integral polytope, that is, the convex hull of some points in $\mathbb{N}^d$.
Let $p_1,\dots,p_m$ be all lattice points in $P$.
Question: What is the condition on $P$ that guarantees ...
- 15.8k
2
votes
0
answers
111
views
Can computers take uniform samples from a polytope?
For each $r \in \mathbb N $ write $\mathbb Z/ 10^r = \{a/10^r: a \in \mathbb Z\}$ and $P(r)$ for the lattice $(\mathbb Z/10^r)^N \subset \mathbb R^N$.
Suppose the plane $P \subset \mathbb R^N$ is ...
- 1,955
8
votes
3
answers
706
views
Rate of growth of an explicit integral
Let $$J_1=\int_0^1\frac{1}{\sqrt{1-t_2}}dt_2,$$
$$J_2=\int_0^1 \int_0^{t_2}\frac{1}{\sqrt{1-t_2}}(\frac{1}{\sqrt{1-t_3}}+\frac{1}{\sqrt{t_2-t_3}})dt_3dt_2,$$
$J_3=\int_0^1 \int_0^{t_2}\int_0^{t_3}\...
- 113
7
votes
1
answer
209
views
Are the primary parallelotopes classified? (equivalently, Voronoi cells of lattices)
A primary parallelohedron is a polyhedron that can fill space with infinite translated copies.
It is known (e.g., Coxeter, H. S. M. Regular Polytopes, 3rd ed. New York: Dover, pp. 29-30, 1973; or, ...
- 1,441
9
votes
0
answers
1k
views
Maximum volume cross-section of a hypercube
This is surely well known, but:
Q1. What is the $(d{-}1)$-dimensional polytope
that realizes the maximum volume cross-section of a unit hypercube
by a $(d{-}1)$-dimensional hyperplane?
...
- 151k
5
votes
1
answer
271
views
Is every triangulation of a Euclidean ball by convex tetrahedra shellable?
Suppose you are given a 3-ball $B$ in $\mathbb{R}^3$ that is bounded by a PL sphere, a triangulation $T$ of $B$ by Euclidean tetrahedra. Is that triangulation necessarily shellable?
I know that if $...
- 10.1k
3
votes
0
answers
102
views
The ring generated by a convex polytope and its faces
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 $V$ with multiplication induced by Minkowski ...
- 3,079
11
votes
1
answer
424
views
Needle probing for a convex body
Suppose there is an unknown closed convex body $K$ of
volume vol$(K) = V$ inside the
unit cube $[-\frac{1}{2}, \frac{1}{2}]^d$ in $\mathbb{R}^d$.
You are permitted to probe with a (one-dimensional)
...
- 151k
16
votes
2
answers
3k
views
Approximating a convex function by a piecewise linear function
Suppose I have a Lipschitz-continuous convex function $f:\mathbb{R}^n\rightarrow \mathbb{R}$. I wish to approximate it on the unit ball by a piecewise-linear function $g:\mathbb{R}^n\rightarrow \...
- 161
4
votes
1
answer
150
views
On necessary condition for no integer points in polytope
For a convex polytope $\mathcal K$ in $\Bbb R^n$ presented by $O(n^c)$ linear inequalities is it true that for $|\mathcal K\cap \Bbb Z^n|=0$ it is necessary that at least one axis of John's ellipsoid ...
- 13.9k
6
votes
0
answers
92
views
Tiling with Horn's polytopes
Let $n\ge2$ be an integer. Consider the hyperplane $H_n$ of ${\mathbb R}^n$ defined by the equation $x_1+\cdots+x_n=0$ and then the sector $P_n\subset H_n$ defined by the inequalities $x_1\le\cdots\le ...
- 52.3k
1
vote
0
answers
65
views
Covering a simplex efficiently by efficiently describable polytopes?
Take a standard simplex or cube in $\mathbb R^n$.
Is there a way to cover it with $O(poly(\log n))$ convex polytopes each describable by only $O(poly(\log n))$ half-plane inequalities?
If not what ...
- 1,826
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
4
votes
1
answer
3k
views
Find the minimum distance between two convex hulls
We work over $\mathbb{R}^N$. Let $\mathbf{P}_1$ denote the hyperplane constructed using $N$ points, each of which is on a different axis (there are $N$ axes). We denote by $\mathbf{P}_2$ the convex ...
- 233
6
votes
1
answer
544
views
Isometric embedding a convex cap to render its boundary planar
I would like to know if there is a polyhedral analog to this beautiful
theorem of Hong:
Theorem 11.0.1.
Any smooth positive disk $(\bar{D},g)$ with a positive geodesic
curvature along $\partial ...
- 151k
3
votes
0
answers
163
views
What is a natural way to extend a function from a subset of vertices to faces?
Let $n$ be a positive integer, and suppose $f$ is a probability distribution on the $2^n$ subsets of $[\![n]\!] := \{1,\ldots,n\}$. What is a "natural" way to extend $f$ to a distribution $\bar{f}$ on ...
- 6,853