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
918
questions
4
votes
1
answer
144
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 ...
3
votes
1
answer
200
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 ...
17
votes
5
answers
858
views
Rigidity of convex polyhedrons in $\mathbb R^3$ with faces removed
Take a convex polyhedron $P$ in $\mathbb R^3$ and remove all the faces, i.e. leave only the edges. Call this graph $E$. Let us now try to continuously deform $E$ in $\mathbb R^3$ so that all the edges ...
28
votes
1
answer
1k
views
Are Minkowski sums of upward closed "convex" sets in $\mathbb{N}^k$ still "convex"? (WAS: Comparing mana costs in Magic: The Gathering)
This was originally a question about comparing mana costs in Magic: The Gathering, but it's turned into a question about Minkowski sums of upward-closed convex sets in $\mathbb{N}^k$. The original ...
4
votes
0
answers
218
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}]$, ...
17
votes
4
answers
737
views
Volume of convex lattice polytopes with one interior lattice point
Let $P$ be a convex polytope in $\mathbb{R}^3$ whose every vertex lies in the $\mathbb{Z}^3$ lattice.
Question: If $P$ contains exactly one lattice point in its interior, what is the maximum possible ...
1
vote
0
answers
121
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 ...
10
votes
3
answers
868
views
Approximate volume computation and lattice point enumeration - hardness
Both volume computation and lattice point enumeration of convex polyhedron are $\#P$ hard. However there is a randomized polytime algorithm for constant factor approximation for volume computation.
...
4
votes
1
answer
121
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 ...
6
votes
1
answer
219
views
Extend space to make polyhedra convex hulls of finite sets
A (convex) polytope is the convex hull of a finite number of points in Euclidean space (this is the so-called "vertex description"). Alternatively, it can defined to be a bounded polyhedron (this is ...
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 ...
5
votes
2
answers
290
views
Convex caps with prescribed edges
Let $P$ be a convex polygon in the plane $R^2=R^2\times \{0\}$, and $E$ be the edge graph of some subdivision of $P$ into convex polygons, which is $3$-connected. Does there exist a convex polyhedral ...
5
votes
2
answers
547
views
When are the closed convex subsets countable intersections of halfspaces
For what kind of topological vector spaces (separable maybe?) are the closed convex subsets countable intersections of halfspaces.
I've seen somewhere that it's true for separable Hilbert spaces, ...
9
votes
1
answer
222
views
Cyclic polygons generalized to higher dimensions
Many theorems hold for cyclic polygons—convex polygons inscribed
in a circle. Perhaps the most basic is this,
from the reference cited below:
Theorem. There exists a cyclic polygon of $n \ge ...
14
votes
0
answers
201
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 ...
2
votes
0
answers
536
views
On Kalai's $3^{d}$ conjecture
I just learned the existence of Gil Kalai's $3^{d}$ conjecture, which according to Wikipedia, is proven for $d$ at most $4$. It states that every $d$ dimensional polytope with central symmetry has at ...
6
votes
2
answers
350
views
Parallelotope fundamental domains of the n-torus
The group $\mathbb Z^n$ acts on the topological space $\mathbb R^n$ by translation: if $z = (z_1, \cdots, z_n) \in \mathbb Z^n$ and $x = (x_1, \cdots, x_n) \in \mathbb R^n$, then $z\cdot x := z+x$. ...
4
votes
2
answers
616
views
How to know if convex-hull of a set contains zero?
Let $(\lambda_1 , \cdots , \lambda_d) \vdash k$ be a partition of $k$ of length $d$. Is there any way to decide if $0 \in \text{Conv}\{(\underbrace{\alpha_1, \cdots, \alpha_1}_{\lambda_1}, \cdots , \...
9
votes
1
answer
407
views
The $32$-deg polynomial for the tetrahedron inscribed in the icosahedron?
This MO answer discusses this table involving the maximal side lengths of the five Platonic solids $T,C,O,D,I$ inscribed in the other solids,
This table is also found in Moritz Firsching's paper. I ...
7
votes
1
answer
285
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....
3
votes
2
answers
291
views
Narayana polynomials as numerators of Ehrhart series rational functions?
The Narayana polynomials (OEIS A001263) are the h-polynomials of the associahedra (the Stasheff polytopes) and their dual simplicial polytopes (cf. the Fomin and Reading ref in the OEIS entry).
Are ...
2
votes
0
answers
67
views
Estimate for the diameter of a facet of best-approximating polytope
Let $P$ be a convex polytope in $\Bbb R^n$ with $N$ vertices that is best-approximating for the Euclidean unit ball $B$ under the symmetric difference metric. I am trying to prove the following ...
8
votes
1
answer
440
views
Loday's characterization and enumeration of faces of associahedra (Stasheff polytopes)
From "The multiple facets of the associahedra" by Loday:
Let us consider the formal power series
$$f(x) = x+a_1 x^2 +a_2 x^3 + \cdots+ a_n x^{n+1} + \cdots$$
and let
$$ g(x) = x+b_1 x^2 + ...
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.$$
...
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
0
answers
212
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 ...
1
vote
1
answer
73
views
Uniqueness of polytope embedding from symmetry group
Do the symmetry group generators of a regular convex polytope and a marked $\{0,1\}^n$ vertex point suffice to embed the polytope uniquely with $\{0,1\}^n$ vertex set?
If so can we find the John's ...
4
votes
0
answers
121
views
Reference for this fact about perturbed polytopes?
Let $K \subset \mathbb{R}^n$ be a polytope (i.e., an intersection of finitely many halfspaces that has finite volume) and consider $F(K) := \int_K \|x\|^2\, {\rm d}x$, where $\|\cdot\|$ is the ...
3
votes
1
answer
285
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 ...
4
votes
1
answer
169
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 ...
5
votes
2
answers
311
views
Convex hull with genus information
Are there convexity generalizations that admit genus information?
For example in genus $1$ is there a way to think of this polyhedron as convex while this polyhedron as non-convex? Any two points can ...
1
vote
1
answer
222
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 $...
2
votes
0
answers
62
views
on vectors for which the intersection of their convex hull and the nonegative orthant is the unit simplex
Consider the vectors $r^1 = (0,2,-1)$, $r^2 = (-1,0,2)$, and $r^3 = (2,-1,0)$. Two properties of these vectors that interest us here are:
1) The $i$'th coordinate of $r^i$ is 0, and
2) The ...
1
vote
0
answers
92
views
quick hull algorithm detail
When using quick hull algorithm to find the polytope for half space intersection, we are required to provide an interior point to the solver qhalf.
In other words, providing
$$Ax \le b$$
is not ...
3
votes
1
answer
155
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)$ ...
0
votes
1
answer
76
views
algorithms and tools available for a particular polytope computation
Let me define each half space i as:
$${H_i}:{c_i}{\bf{x}} \le {b_i}$$
The intersection of all such ${H_i}$ gives a polyhedron (bounded or not). Suppose I am interested in if ${H_i}$ is active (...
2
votes
0
answers
76
views
An inequality about the volume of convex body
For a subset $S$ of $\mathbb{R}^n$, we denote by $\lambda S$ the dilation for any $\lambda \in \mathbb{R}$:
$$\lambda S=\{\lambda x| x\in S\}.$$
Let $\Omega$ be a convex body in $\mathbb{R}^n$ with $...
0
votes
1
answer
28
views
Finding a point at which only certain linear functionals are integral
Let $C$ be a full-dimensional rational polyhedral cone in $\Bbb R^d$ with facets $G_1,\ldots,G_n$ . For each $i$, let $h_i$ be an integer-valued linear functional on $\Bbb R^d$ whose kernel is the ...
6
votes
0
answers
188
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 ...
4
votes
1
answer
567
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: ...
4
votes
0
answers
80
views
Polynomial approximations on the Boolean hypercube
Given $\vec{a} \in \mathbb{R}^n$ and $b \in \mathbb{R}$ consider the function $f(x) = Th[\vec{a}.\vec{x}+b]$ on $x \in \{-1,1\}^n$ such that the ``threshold function (Th)" gives $1$ when the argument ...
1
vote
0
answers
353
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-...
5
votes
0
answers
219
views
Is there a well-established terminology for polyhedra/polytopes?
I got confused lately. It seems like in the metric context a polyhedron tends to mean an intersection of a finite number of half-spaces, while a polytope is a convex hull of a finite set of points. At ...
0
votes
1
answer
79
views
Can convex combinations of indicator functions for pairwise non-disjoint sets unordered by inclusion dominate one another?
Let $N$ be a finite subset of the naturals. Let $P$ be a set of subsets of $N$ such that:
1) $P\neq \varnothing$,
2) $\forall x\in P, |x| >1$,
3) $\forall x,y\in P,$ if $x\neq y$, then $x\not\...
0
votes
2
answers
304
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$ ...
1
vote
0
answers
61
views
Sampling in a polyhedral complex
Assume one is given a polyhedral complex $P$ in $\mathbb{R}^n$. Now consider picking uniformly at random a $D \subseteq \{0,1\}^n$. Is there way to upper bound the probability that $D$ (a subset of ...
2
votes
0
answers
162
views
Link of a power series by the Bernoullis for a Riccati equation to zonotopes?
On pg. 85 of The Rise and Development of Theory of Series up to the Early 1820s by Ferraro is a series soln. of
$$ d^2z/z = -x^2dx^2 $$
related to the reputed first appearance of a Riccati-type eqn.,...
15
votes
3
answers
988
views
Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?
Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets.
Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.
Can $\text{Proj}(P)$ have more than $f$ facets?
...
54
votes
5
answers
2k
views
Unusual symmetries of the Cayley-Menger determinant for the volume of tetrahedra
Suppose you have a tetrahedron $T$ in Euclidean space with edge lengths $\ell_{01}$, $\ell_{02}$, $\ell_{03}$, $\ell_{12}$, $\ell_{13}$, and $\ell_{23}$. Now consider the tetrahedron $T'$ with edge ...
5
votes
0
answers
128
views
Lattice paths in polytopes
Let $P$ be a polytope in $\mathbb{R}^n$. Let $A_ix = b_i$ be the defining equations of its codimension $1$ faces. Is there an algorithm or some kind of criterion to decide if the lattice points inside ...