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

learn more… | top users | synonyms

3
votes
1answer
167 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 ...
5
votes
2answers
246 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 ...
0
votes
2answers
260 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 ...
2
votes
1answer
356 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| \, ...
1
vote
1answer
166 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 ...
15
votes
1answer
355 views

Does every convex polyhedron have a combinatorially isomorphic counterpart whose all faces 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 ...
2
votes
1answer
173 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 ...
6
votes
1answer
322 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
2answers
234 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 ...
3
votes
0answers
103 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 ...
1
vote
2answers
245 views

Secondary Polytope Simplicial?

Is the secondary polytope of a simplicial polytope necessarily simplicial?
1
vote
1answer
126 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 ...
9
votes
2answers
1k 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}, ...
5
votes
0answers
218 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 ...
2
votes
0answers
43 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 = ...
8
votes
0answers
183 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 ...
3
votes
3answers
422 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 ...
2
votes
2answers
137 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 ...
16
votes
2answers
415 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 ...
4
votes
1answer
215 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 ...
1
vote
2answers
237 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 ...
3
votes
1answer
291 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
votes
1answer
185 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, ...
2
votes
2answers
442 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 ...
1
vote
0answers
175 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, ...
40
votes
0answers
1k 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 ...
11
votes
0answers
391 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 ...
2
votes
2answers
206 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 ...
1
vote
0answers
159 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", ...
8
votes
2answers
381 views

symmetries and faces of the associahedra

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-skeleton ...
3
votes
3answers
420 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 ...
9
votes
1answer
709 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 ...
3
votes
1answer
240 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 ...
4
votes
2answers
313 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? ...
13
votes
1answer
384 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 ...
1
vote
2answers
538 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. ...
19
votes
4answers
677 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 ...
1
vote
1answer
377 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 ...
0
votes
0answers
107 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 ...
2
votes
1answer
498 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 ...
5
votes
0answers
95 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 ...
4
votes
1answer
182 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 ...
1
vote
1answer
184 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, ...
4
votes
1answer
795 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 ...
3
votes
0answers
89 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 ...
3
votes
2answers
304 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?
17
votes
4answers
748 views

The Constructions of Davis and Januszkiewicz

One of the most useful tools in the study of convex polytope is to move from polytopes (through their fans) to toric varieties and see how properties of the associated toric variety reflects back on ...
2
votes
2answers
168 views

4-polytope with vertices at the binary octahedral group

Does anybody know if there is a convex polytope in $R^4$ with vertices at the binary octahedral group (identitfying $H$ with $R^4$). The binary tetrahedral group lies at the vertices of the ...
2
votes
1answer
151 views

How can pushing a vertex in a polytope lead to merging facets?

I'm trying to understand the Lemma 2.2 and Corollary 2.3 of Francisco Santos paper "A counterexample to the Hirsch conjecture": http://arxiv.org/abs/1006.2814 Corollary 2.3 is a proof of a result of ...
27
votes
4answers
1k views

Probability of zero in a random matrix

Let $M(n,k)$ be the set of $n\times n$ matrices of nonnegative integers such that every row and every column sums to $k$. Let $P(n,k)$ be the fraction of such matrices which have no zero entries, ...