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
13
votes
1
answer
1k
views
When is a matrix similar to a non-negative matrix?
Consider a real square matrix $A$ of size $n\times n$. Under which conditions on $A$ does there exist a row-stochastic matrix $U$ (non-negative, rowsums = 1), such that $A'=U^{-1}AU$ is a non-negative ...
- 231
3
votes
1
answer
201
views
Simplex with edges of length at least s having smallest circumradius
Is it true that of all $n$-simplices with edge lengths greater than or equal to some parameter $s$, the regular simplex with edge lengths $s$ has the smallest circumradius? It seems obvious, but I ...
- 185
5
votes
2
answers
368
views
Diameter-area ratio for affine tranformations.
Consider an convex plane figure $F$. How to prove that there is an affine transformation $a$ such that $\sqrt{3}$ diameter$(a(F))^2\leq 4$ area$(a(F))$?
I found only one reference, to "Über einige ...
- 5,063
1
vote
2
answers
431
views
Higher dimensional convex hull
Let $CH(S)$ be a convex hull of a finite set $S$ and denote the set of all the vertices of $CH(S)$ as $Vert(S)$. For a vertex $v \in Vert(S)$, it has an associated set $E(v)$ which is defined as $E(v)=...
user33954
2
votes
3
answers
2k
views
non-convex Polytope definition
I have a simple question. I read that given a vector space $N_{\mathbb{R}}$ over $\mathbb{R}$,
we can define a convex polytope in the following way:
$$P:= \Big\{ \sum_{u\in S} \mu_u u \,\Big| \, \...
- 335
1
vote
1
answer
187
views
Straight Line Passing Through a Convex Region
Is there any test to tell me whether a straight line in a 3D euclidean space passes through a bounded closed convex region? To focus on a more specialised version of the problem, you can assume that ...
- 113
25
votes
3
answers
994
views
Does every convex polyhedron have a combinatorially isomorphic counterpart whose faces all have rational areas?
Does every convex polyhedron have a combinatorially isomorphic counterpart whose faces all have rational areas?
Does every convex polyhedron have a combinatorially isomorphic counterpart whose edges ...
- 513
2
votes
1
answer
579
views
Does the Border (Boundary) Points of a convex body make a concave function?
Let $\mathbb{S}$ be a closed and bounded convex body in 2-D with some non-empty intersection with positive quadrant and let it also contain origin. Let $c>0$ be the right-most point on the x-axis ...
- 1,421
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 ...
3
votes
2
answers
270
views
Formalization (and background) of a formula, concering the integral points of a polygon.
I have recently become aware of the following neat statement.
Consider a convex polygon $P$ in the real plane with integral vertices. If we associate with every integral point $(a,b)$ the monomial $x^...
- 3,513
3
votes
0
answers
188
views
Covering points with a convex hull
Consider a set of $n$ points $x_1,\ldots,x_n \in \mathbb{R}^d$, for some $n \gg d$. Suppose $\{x_1,\ldots,x_n\} \subset C \subset \mathbb{R}^d$. Say that a set of points $y_1,\ldots,y_m \in C$ covers $...
- 794
2
votes
2
answers
624
views
Secondary Polytope Simplicial?
Is the secondary polytope of a simplicial polytope necessarily simplicial?
- 360
2
votes
1
answer
223
views
Decide inside/outside convex hull using only distances in graph
Given a weighted, undirected graph G with K knodes k1 … kK. I have a K times K matrix containing the shortest distances between each pair of points.
Is it possible (if yes how), to decide if a point ...
- 21
21
votes
2
answers
8k
views
How many vertices can a convex polytope have?
One has an $n$-dimensional convex polytope $P$ represented by an intersection of half-spaces:
\begin{equation}H_i = \{ (x_1,x_2, \ldots,x_n) \in \mathbb{R}^n \mid \sum_{j=1}^n a_{ij} x_j \ge a_{i0}, \...
- 251
5
votes
0
answers
324
views
Lattice points inside a (n-dimensional) tetrahedron
Hi, overflowers.
I was interested in a sharp lower bound for the number of lattice points (say, integral lattice points) inside the tetrahedron defined by the coordinate hyperplanes and $x_1/a_1+...+...
- 306
2
votes
0
answers
51
views
Conditions under which a set of points have a low weight representation under some basis
Let $S \subset R^d$ be a convex polytope in $d$ dimensional real space. Say that $S$ has weight $w$ if there exists some basis $x_1,\ldots,x_d$ such that for every point $v \in S$, we can write $v = \...
- 794
13
votes
0
answers
252
views
Does there always exist a self dual polytope that contains a given polytope contained in its dual?
Suppose a polytope $P$ is contained in its dual polytope $\tilde{P}$. Does there always exist a polytope $Q$ that contains $P$ and is self dual $Q=\tilde{Q}$? Is there any bound on the minimal number ...
- 241
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
3
votes
2
answers
247
views
determining a convex set by mixed volumes
For a convex set $K \subset \mathbb{R}^2$ let $\phi_K:$ convexsets in $\mathbb{R}^2 \rightarrow [0,\infty), A \mapsto MV(A,K)$. Where by $MV(A,K)$ I mean the mixed volume of $A$ and $K$ in the ...
- 41
16
votes
2
answers
536
views
What is $A+A^T$ when $A$ is row-stochastic ?
This is motivated by this MO question.
If $A\in{\bf M}_n({\mathbb R})$ is row-stochastic (entrywise non-negative, and $\sum_j a_{ij}=1$ for all $i$), then $M:=A+A^T$ is
symmetric,
entrywise non-...
- 52.3k
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
2
votes
2
answers
457
views
Volume of intersection of a convex polytope with an affine space.
Given an $n$-dimensional polytope $P\subset \mathbb{R}^n$.
For a subset of indices $i_1,\ldots,i_k$ of $\{1,\ldots,n\}$ and reals $a_1,\ldots,a_k$, we denote by $P(x_{i_1}=a_{1},\ldots,x_{i_k}=a_{k})...
4
votes
1
answer
510
views
moduli space of polytopes
When considering classification problems about polytopes, I sometimes has the feeling that one need to talk about certain parametrized families, i.e. moduli space of such polytopes. But neither do I ...
- 3,472
3
votes
1
answer
258
views
Classification of lattice polytopes with small number of lattice points in the facets
Suppose $P$ is a convex lattice polytope in $Z^3$ without interior lattice points, and we require the interior lattice points of each facet(i.e. dimensional 2 faces) are neither too much nor too few, ...
- 3,472
2
votes
2
answers
1k
views
Convex upper bound on a linear-fractional function
I have a function of the form $f(x,y) = \frac{x}{c+y}$ where $c$ is a positive constant, $c \ge x \ge 0$, and $y \ge 0$. I would like to find a convex upper-bound for this function. Is there a ...
- 362
1
vote
0
answers
193
views
Lattice-point enumeration question involving linear combinations of matrices
I would like to know some references to learn more about an answer to this question, if there are any references:
Let $A_1, \dots , A_m$ and $B$ be $n\times n$ symmetric matrices. Let $$S = \{(x_1, \...
- 170
56
votes
1
answer
3k
views
Intersecting family of triangulations
Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let $\...
- 24.7k
15
votes
2
answers
3k
views
Given the vertices of a convex polytope, how can we construct its half-space representation?
Let us say I have the vertices of a polytope $V = \{v_1,\dots,v_k\} \subset \mathbb R^n$. Is it possible to write $V$ as intersection of half-spaces using the information from the vertices, i.e., can ...
- 173
12
votes
0
answers
533
views
Reciprocity (Ehrhart-style) for real polytopes?
Is there some sense in which the well-known Ehrhart reciprocity law for rational, convex, polytopes can be extended to any convex polytope with arbitrary real vertices?
In other words, given any ...
5
votes
2
answers
656
views
Is there a simple test to determine whether a polytope is integral?
It is known that any rational convex polytope expressed as $\{ x\in\mathbb{R}^d : Ax \ge b \}$, where $A\in\mathbb{Z}^{k\times d}$ and $b\in\mathbb{Z}^k$, can be written as the convex hull of finitely ...
- 170
15
votes
3
answers
1k
views
Classification of Platonic solids
My question is very basic: where can I find a complete (and hopefully self-contained) proof of the classification of Platonic solids? In all the references that I found, they use Euler's formula $v-e+...
- 955
1
vote
0
answers
185
views
Compute generalized pentagram map
Hi,
(This is my first question on MathOverflow! :-)
Imagine you have a set of points $S = \{p_1, \ldots, p_n\}$ in $\mathbb{R}^d$, of which $t$ are "bad". I want to compute a "safe convex hull", ...
- 11
10
votes
2
answers
691
views
Symmetries and faces of the associahedron
The dihedral group of order $2n+2$ acts on $K_n$, the ($n-2$)-dimensional associahedron. Are there any other symmetries? References?
Does the answer to 1 change if we restrict to just the 1-...
- 1,625
4
votes
1
answer
4k
views
H-representation versus V-representation of polytopes
The H-representation of a convex polytope $S$, is just a set of linear inequalities corresponding to the intersection of halfspaces:
$S = ( x | Ax\leq b )$.
One could also represent a convex polytope ...
- 45
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
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
3
votes
1
answer
356
views
Empty convex polytopes for random point sets
I know of the famous results on the Erdős-Szekeres empty convex polygon problem in the plane
(the Happy-Ending Problem), and I know that there are higher-dimensional extensions.
A great source (...
- 151k
4
votes
2
answers
567
views
Realization spaces for regular convex polytopes
Q1.
Are there convex polytopes combinatorially equivalent to each of the regular polytopes
that are realized with integer vertex coordinates?
&...
- 151k
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
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.
...
25
votes
4
answers
1k
views
Do random projections (approximately) preserve convexity?
The Johnson-Lindenstrauss lemma implies that any set of $k$ points in $\mathbb{R}^d$ can be randomly projected into $d' \approx \log(k)/\epsilon^2$ dimensions such that the distances between each pair ...
- 253
1
vote
1
answer
2k
views
Question regard checking convexity by "restriction to any line that intersects the function domain"
Hello all,
I have a question (probably stupid one) about the fact that " A function is convex if and only if it is convex when restricted to any line that intersects its domain".
In Stephen Boyd and ...
- 43
0
votes
0
answers
155
views
Area of spherical polygons in high dimensions
Given 4 points on $S^3$. If we look at the spherical polygon formed on $S^3$, is there a formula for the 3-dimensional Hausdorff measure for it?
E.g.: When I tried to set up a spherical coordinate ...
- 113
2
votes
1
answer
2k
views
Proving that a specific function is quasiconvex
Hello all,
Assume we have a sequence of quasiconcave functions (in $X$) denoted by $f_{i,j}(X)$ for $i,j = 1,\ldots,n$. Denote by $F(X)$ the $n\times n$ matrix whose $(i,j)$ entry is the function $f_{...
- 43
5
votes
0
answers
104
views
Regularity of simplices, part deux
This question is directly inspired by Pietro Majer's question and my answer to it.
One can define a simplex, and the dihedral angles thereof in an infinite dimensional Hilbert space (one has to take ...
- 96.4k
5
votes
1
answer
243
views
Regularity of simplices
A triangle is regular, provided it is equilateral, or, also, equiangular. How these conditions generalize to characterizations of regularity of simplices?
In particular, it turns out that
a ...
- 60.5k
1
vote
1
answer
288
views
Realizing not-quite-barycentric subdivision of a polytope
Given a poset $S$, one can form a new poset $I(S)$ whose elements are intervals in $S$ (i.e. either $\emptyset$ or $[a,b]$ for some $a\leq b\in S$) with ordering by (set) inclusion. If $S$ is ranked, ...
- 3,093
4
votes
1
answer
1k
views
Complexity of convex polytope volume calculation ? (Volume of Voronoi cell) (Error probability)
Assume I have polytope in R^k given by N (k<< N) linear inequalities (A_i x < b_i).
I guess complexity of its volume calculate is higher than linear in "N", am I right ?
(Is the complexity ...
- 24.9k
3
votes
0
answers
102
views
Versions of Helly's Theorem for Unbounded Parallelpipeds
I'm studying Frobenius splitting of toric varieties based on Sam Payne's characterization of Frobenius splitting ("Frobenius splittings of toric varieties" (2008)) and I came across a sort of Helly's ...
- 31
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