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
6
votes
2
answers
2k
views
Birkhoff's theorem about doubly stochastic matrices
Birkhoff's theorem states:
The set of $n \times n$ doubly stochastic matrices is a convex set whose extreme points are the permutation matrices
This theorem seems to be commonly attributed to ...
- 28.6k
4
votes
4
answers
594
views
Upper bound for the number of subsets of N points which exhaust their convex hull
Hello.
Looking at a set S of N points in the plane, I call a subset B of S "legal" if the set of points contained in the convex hull of B is exactly B itself. In other words, a subset B of S in legal ...
uuu
7
votes
1
answer
224
views
A polytope with a bound on the sum of any $k$ variables
Let $2\le k\le n-1$ and define the polytope
$$P_k(n) = \lbrace (x_1,\ldots,x_n) \in \mathbb{R}^n :
-1\le x_{i_1}+\cdots +x_{i_k} \le 1 \text{ for all } 1\le i_1\lt\cdots\lt i_k\le n\rbrace.$$
There ...
- 37.7k
1
vote
0
answers
44
views
In convex optimization we know that the optimum solution is on which hyper plane
We have a standard linear program, I mean a set of inequalities $c_i^Tx\leq b_i$ where $i\in \{1,\ldots ,k\}$ and we want to find $max\{c^Ty| y\in \{\cap \{x|c_i^Tx\leq b_i\}\}$. I put some condition ...
- 19
2
votes
1
answer
367
views
Angle between Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample
Definitions
Let $\mathcal{C}$ be a convex polytope in $\mathbb{R}^{D}$ with $K$-facets
$F_{1},\ldots,F_{K}$. I denote the normal vector of the $k^\mathrm{th}$ facet as
$\mathbf{w}\_k=(w_{k1},\ldots,...
- 111
7
votes
1
answer
216
views
How to prove the existence of the polytope in $\mathbb{R}^d$ with a given number of faces, minimizing the isoperimetric ratio?
This is the isoperimetric type question. We know that in $\mathbb{R}^d$, balls are the sets that minimize the isoperimetric ratio $\frac{S^{d}}{V^{d-1}}$, where $S$ is the surface area and $V$ is the ...
- 1,350
3
votes
0
answers
259
views
Lattice points in regular simplex
Suppose we are given a regular (closed) simplex $S$ in a vector space $V$ of dimension $n$, whose vertices have integer values. Then for a lattice $L$, is there a sufficient criterion, for $S$ to ...
- 131
0
votes
1
answer
79
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 (...
- 867
4
votes
1
answer
367
views
convex polyhedron in the unit cube
Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where $\...
- 165
5
votes
2
answers
879
views
Intersection homology for toric varieties
is there any algorithm known for computing (middle perversity)intersection homology of complex toric varieties based on their combinatorial data? I'm not looking for a computer program.
Regards,
...
- 93
3
votes
2
answers
175
views
Polytope with indegree-increasing property.
I have a question about a simple polytope.
I am worried that my question would be inappropriate for mathoverflow.
So I am sorry that I am ignorant of combinatorics.
Let $\mathcal{P}$ be a simple ...
- 1,037
1
vote
0
answers
43
views
Quantitative error control in Minkowski-Stein formula
Let $K\subseteq\mathbb R^d$ be a compact convex body with non-empty interior, and $E$ be a $(d-1)$-dimensional linear subspace of $\mathbb R^d$. Let $\theta\in\mathbb R^d$ be the unit vector such that ...
- 373
9
votes
1
answer
261
views
Do there exist "expanding" $1$-skeletons of simple $4$-polytopes?
Let $\{ G_n \}_{n \ge 1}$ be a sequence of graphs such that the number of vertices of $G_n$ tends to $\infty$ as $n \to \infty$. We say that $\{ G_n \}_{n \ge 1}$ is an expander family if
$\lambda_2( ...
- 7,857
5
votes
2
answers
149
views
Inscribed parallelotope in a $d$-simplex
The problem setup is simple: Given a $d$-simplex $\Delta_d:=\{(x_1,\cdots,x_d):x_i\geq 0,\sum_i x_i\leq 1\}$, can we construct a finite sequence of parallelotope $A_i$ so that $\Delta_d=\cup_{i=1}^N ...
- 599
2
votes
1
answer
739
views
faces of a polytope
Let $a_1,a_2,..,a_n\in\mathbb{R}^m$, $n>m$ and the points are in general position meaning, no hyperplane contains more than $m$ points. Define a polyhedron $$P=\{x\in\mathbb{R}^m:a_1'x\leq0, a_2'...
- 31
8
votes
1
answer
543
views
What's the best way to test if a sphere is a polytope? (algorithms for the Simplicial Steinitz Problem)
The problem of recognizing whether a simplicial face lattice is polytopal is sometimes called the Steinitz problem.
Sturmfels and Bokowski advanced a set of methods in the late 80s to test whether ...
- 103
3
votes
1
answer
804
views
Approximation of a convex body by a contained polytope
This question deals with approximating a convex body (a compact convex set of $\mathbb{R}^d$ with non-empty interior) by convex polytopes.
For a given $\delta$, let $n_\delta$ be the number of faces ...
- 591
9
votes
0
answers
180
views
Is every planar point set the projection of vertices of a neighborly 4-polytope?
More exactly, written in coordinates, I'm curious to know if for every point set $(x_i,y_i)$ there are $(x_i,y_i,z_i,w_i)$ that are vertices of a neighborly polytope.
This problem comes from a simple ...
- 301
1
vote
1
answer
153
views
Counting faces on multipermutahedra/multipermutohedra
A multipermutahedron is the convex hull of all permutations of a list of numbers. For example, $\Pi(0,1,2)$ generates a regular hexagon, and $\Pi(0,1,1,2)$ generates a cuboctahedron.
In general, ...
- 363
2
votes
0
answers
68
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 ...
- 216
8
votes
1
answer
231
views
Classifying two-faces of four-polytopes
Motivation: This question is related to my study of hyperbolic Coxeter polytopes. In general, if one put some restrictions on the type of their dihedral angles (say, all dihedral angles are equal to $\...
- 1,268
3
votes
0
answers
128
views
Stellar moves on pairs of polyhedra
Let $P$ and $Q$ be polyhedra of $\mathbb{R}^n$ with $Q \subset P$. Let $(M,N)$ and $(M',N)$ be pairs of abstract simplicial complexes.
Consider two triangulations
$$f\colon (|M|,|N|) \to (P,Q)$$
...
11
votes
1
answer
558
views
doubly-stochastic isomorphisms of graphs
A doubly stochastic matrix that commutes with the adjacency matrix of a graph is a doubly-stochastic automorphism of that graph (definition by Tinhofer 1986). Each (classical) automorphism of a graph ...
- 3,388
5
votes
1
answer
518
views
The number of facets of a polyhedron under linear transformation
Consider a (not necessarily bounded) convex polyhedron $P\subset \mathbb{R}^n$ which has $k$ facets.
Let $L:\mathbb{R}^n \to \mathbb{R}^m$ be a linear transformation.
Question1: Is there a fixed ...
- 1,991
1
vote
2
answers
570
views
Hales's fan associated with a polyhedron
In Hales's book (cited below), he associates what he calls a fan with any convex polyhedron in $\mathbb{R}^3$.
I will not define his notion of fan, but let his figure (p.137) serve as a definition:
...
- 151k
2
votes
3
answers
596
views
a different algebra/representation for convex sets
Hi,
I was dealing with finding a feasible region for a set of norm inequalities and the feasible region is convex. The question is not about how to find the feasible region but how to represent the ...
- 21
5
votes
2
answers
153
views
Expressing a convex Polytope as a sublevel set of a function
Given an n-dimensional polytope $P$ in $\mathbb R^n$, Given as a convex hull of a finite set of points, $S$ I would like to construct an expliict formula for a function $f\colon \mathbb R^n \to \...
- 1,893
1
vote
0
answers
93
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 ...
- 867
5
votes
2
answers
253
views
name for a polytope constructed from a system of linear equations?
To a system of inhomogeneous linear equations, one can associate a polytope, as follows. Let $A\in\mathbb{R}^{m\times n}$,
$b\in\mathbb{R}^m$ and $V=\{x\mid Ax=b, \text{support of $x$ minimal}\}\...
- 14k
8
votes
3
answers
2k
views
Listing lattice points in a simplex
Let $n \in \mathbf{Z}_{\geq 1}$. Is there an algorithm which, given a simplex $\Delta \subset \mathbf{R}^n$ specified as the convex hull of $v_0,\dots,v_n \in \mathbf{Z}^n$, computes the set $\Delta \...
- 3,009
2
votes
0
answers
415
views
Find the intersection between two convex hulls, in this specific case
We work over $\mathbb{R}^K$. Let $V$ be the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$.
Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ ...
- 233
7
votes
2
answers
1k
views
Maximal Ellipsoid
John's Theorem can be stated as "To every compact, convex body, there is a unique inscribed ellipsoid, whose volume is maximal among all inscribed ellipsoids." It goes on to classify this maximal ...
- 1,588
9
votes
0
answers
204
views
Positivity of coefficients of Ehrhart polynomial of n-Tetrahedron
A set of positive integers $d_1, \dots, d_n$ describe two n-dimensional closed lattice tetrahedron:
$$ T = \left\{ (x_1, \dots, x_n) \in \mathbb{R}^n: \sum_{i=1}^n \frac{x_i}{d_i} \leq 1 \textrm{ and ...
- 909
6
votes
1
answer
269
views
two-dimensional sections of polyhedral cones
Given a polyhedral cone, its intersection with any two-dimensional plane is either a polygon or a region enclosed by a polygonal curve. Is it a characterization of polyhedral cones? Does there exists ...
- 71
4
votes
2
answers
238
views
time-shifted ODEs/volume of polytopes
Hello,
I'm looking for help with the following ODE:
f'(t) = x f(1 - at)
for 0 < a < 1, x in any interval (though 0 < x < 1 would be best), and f(0) = 1. There should be a solution for $...
- 105
6
votes
3
answers
312
views
Inequality of arithmetic and geometric means for the lattice polytopes?
Let $K$,$L$,$M$ be convex lattice polytopes (so their vertices are in $\mathbb{Z}^n$) in $\mathbb{R}^n$ satisfying $K+L\subseteq M+M$ (Minkowski sum). Do we always have
$$|K\cap\mathbb{Z}^n|\cdot|L\...
- 157
2
votes
0
answers
78
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 $...
- 179
4
votes
1
answer
271
views
On a conjecture by Hibi regarding h-vectors
For integral polytopes, it is conjectured (T. Hibi), that if the $h^*$-vector is symmetric, then it is also unimodal (increasing, then non-decreasing).
A non-integral polytope do not, in general, ...
- 15.8k
7
votes
1
answer
466
views
Does every simplicial polytope have a topology-preserving contractible edge?
An edge of a triangulated manifold is said to be contractible if it may be contracted to a vertex without modifying the topological type of the underlying manifold. Otherwise, the edge is ...
1
vote
2
answers
1k
views
Does Euler's formula imply bounds on the degree of vertices in a 3-polytopal graph?
A corollary of Euler's formula tells us that the edge-vertex graph of every convex 3-polyhedron must have a face with either 3, 4, or 5 edges, using an argument about the average degree of vertices.
...
4
votes
1
answer
320
views
Seeking criteria for "threadable" pairs of centrosymmetric polyhedra
Let $A$ and $B$ be origin-centered centrosymmetric polyhedra in $\mathbb{R}^3$:
"for every point $(x, y, z)$ [...] there is an indistinguishable point $(-x, -y, -z)$."
Say that $A$ and $B$ are ...
- 151k
3
votes
0
answers
182
views
Zeros of Hilbert series of affine toric varieties
Consider a convex rational polyhedral cone $C\subset\mathbb R^m$ with vertex at the origin. Let $X$ be the corresponding affine toric variety, i.e. $\mathbb C[X]=\mathbb C[\mathbb Z^m\cap C^\circ]$. ...
- 3,513
4
votes
1
answer
258
views
The Mahler conjecture and non-zonoidal 3-polytopes (4-polytopes)
I have been working on the Mahler conjecture for over a year now and have made some progress for certain classes of convex polytopes and I'm now attempting to write up my results specified to $\mathbb{...
- 1,441
0
votes
2
answers
2k
views
Finding a bounding volume (line segments) from a kDop definition.
I have a problem.
I'm trying to recover a bounding volume (actually line segments that form the bounding volume) from a kDop definition (in a 3D space). (its to draw the kDop on screen)
In my kDOP ...
- 3
3
votes
0
answers
148
views
Average nastiness of a Newton polytope
Given a Newton polytope $P$ inside the $d$-scaled simplex ( i.e $\alpha \in P \implies | \alpha |=d $ ), then we define the following quantity:
$$ P(x)= \left( \sum_{\alpha \in P} \binom{d}{\alpha}...
- 351
8
votes
2
answers
383
views
Do singular values of a point set determine its shape?
Suppose I have $k$ points in $d$ dimensions. Let A be a $k\times d$ matrix with $i$th row giving the coordinates of $i$th point. Do singular values of this matrix have an interpretation as some kind ...
- 2,242
3
votes
1
answer
409
views
Looking for a canonical (matroid polytope) subdivision of the hypersimplex
A matroid polytope is the convex hull of the indicator vectors of the bases of a matroid, and a matroid polytope subdivision (MPS) is a polyhedral subdivision of a matroid polytope whose cells are ...
- 902
1
vote
2
answers
695
views
Volume of normal cone of a simplex (at a vertex)
This question is related to an orthant-type simplex in $\mathbb{R}^n$, which can be defined as
$$ S = \{x\in\mathbb{R}_{+}^n: \sum_{i=1}^nx_i \leq 1\}=\overline{\mbox{conv}}(0,e_1,\ldots,e_n). $$
For ...
- 980
2
votes
1
answer
384
views
Hypercube vertex sampling with largest convex cone
Maybe this question was already asked and forgive me if I can't formulate it well.
Lets assume we have a n-dimensional hypercube. If we want the smallest set of vertices such that the cube is inside ...
- 295
3
votes
2
answers
828
views
Counting integral points of a polytope in R^3 (the c_1 coefficient of Ehrhart polynomial)
(Sorry I'm outsider in this field.)
I need to count the number of integral points in a convex polytope in $\mathbf{R}^3$. The cones in the dual fan are not necessarily regular (does it create any ...
- 2,232